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;
- logarithmic in N
- linear in N ()
- linearithmic in N
- 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?