Big O complexity of simple for not always linear?

Question

I'm sure most of you know that a nested loop has O(n^2) complexity if the function input size is n

for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
...
}
}

I think that this is similar, by a analogous argument, but i'm not sure can anyone confirm?

for(int i = 0, max = n*n; i < max; i++{
...
}

If so i guess that there is some kinds of code whose big O mapping is not immediately obvious besides recursion and subroutines.

Answer 1

Depends on what do you mean by "simple". A divide-by-two search in a sorted array of size n can be written as a non-nested for loop, too, but it would have O(log(n)) time. And like you rightly said, a for loop from 0 to n*n would execute in O(n*n) time.

Yes, there are codes where running time is not immediately obvious. Even more, there's code out there where the effect and even purpose is not immediately obvious, too :)

Answer 2

It's still O(n) - except that your "n" in this case is "n*n". You've simply increased the value of n - not the complexity of the loop.

Answer 3

If m = n^2, then a "simple for" is certainly linear in m. If you'd like to argue that this is n^2, please go ahead.

The Big-O notation is counting operations here. If you're performing n^2 of them, I'm not sure what reporting the sum as n^2 tells you, because you're performing m operations.

Your proposal doesn't make sense to me. It's misleading about the true name of that sum. The correct way to say it is O(m).

Answer 4

Your basic simple loop is always O(m) where m is the upper bound on the iterations. But your m is really n*n, so it's O(n^2).