Asymptotic running time of for-loops

Question

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
4. quadratic 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?

Answer 1

The definition of asymptotic running times is... well asymptotic. That is, it is the behavior of the function as N is very very large. The behavior of the function at smaller N is irrelevant. In this case, as N is very very large, it is larger than 1000. That means that the code inside the if clause is actually completely irrelevant as far as asymptotic running time goes (Note: I'm not sure why you said the else statement is run "most" of the times if N is really high, it's clearly run "all" the times when N is really high). All that matters is the code in the else.

Note, the "worst case" you're thinking of is legitimate in the cases of sequential operations. That is, if there was no if-else block, but both branches of the code were simply executed all the time, then what you said would be exactly correct: If you run code that is quadratic in N followed by code that is linear in N, the overall code is quadratic, as you said.