# Asymptotic running time of for-loops

I have this question which I need answered:

What is the asymptotic running time for the following piece of code?

``````if (N < 1000)
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
A[i] = j;
else
for (int i = 0; i < N; i++)
A[i] = i;
``````
1. logarithmic in N
2. linear in N ()
3. linearithmic in N

And the correct result is “2. linear in N” which I can't figure out why, since that as far as I've understood, we want to accept the worst case>best case.

The worst case here is that the if statement is run and the time would then be quadratic in N. I am aware that we're trying to find some kind of average of more attempts, but how can I know what the value of N is? If N is really high (10000), it's obviously the else statement that is run most of the times. But can we assume this or have I misunderstood something?

• @Euphoric One could argue that in the above code, `N` is a variable - an untyped variable no less. Providing the type definition would eliminate all guesswork. Also, if we interpret `N` as the set of natural numbers, then it sometimes means `0` is included as well, and zero is not positive or negative. Simply saying `N = {0, 1, 2, ...}` would similarly remove guess work. – Shaz Aug 18 '14 at 14:22