0

I know time complexity for nested loop of n is O(n^2). But If I have the nested loop of as below,

for(i=0;i<n/2;i++)
  for(j=0;j<n/2;j++)
    ...
    ...

How to calculate time complexity for this code. Is it also O(n^2)? If it is, how?

Smith Dwayne
  • 2,675
  • 8
  • 46
  • 75
  • this is the same complexity as if you were dividing by 1, i.e. not dividing, as the number you are dividing by is a constant number. You could divide it by a million, and the complexity is still O(n^2). If, however, you divided it by n, or a derivative of n, it would change. E.g. `for (i = 0; i < n/(n/2); i++)....` it would have a different complexity. – AndrewP Oct 16 '18 at 03:35

1 Answers1

1

Is it also O(n^2)? If it is, how?

Yes, it is.

All you have to do is count the total number of iterations (which is n/2 * n/2 = n^2 / 4 by the product rule), and bear in mind that Big-O notation ignores constants. Asymptotic analysis drops constants because they don't matter when n tends to infinity. In other words, f(n) = n and g(n) = 2n are both linear functions, despite the fact that g grows faster than f. Asymptotic analysis only cares about classes of growth rates.

See also:

Miljen Mikic
  • 14,765
  • 8
  • 58
  • 66