2

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?

6

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.

  • 1
    I always hated questions like this because i thought of the entire number range negative infinity to positive infinity. The type does not specify unsigned, nor does the question specify a starting point or conditions on the input such as N being positive. – dietbuddha Aug 17 '14 at 15:37
  • 2
    Thanks a lot for the good answer, and yes I meant all the time and not only "most". I did not know that you shall expect N to be really large, but now that you've told me, everything makes sense. Thanks again. – owwyess Aug 17 '14 at 15:44
  • 2
    @dietbuddha Computational complexity theory defines N as positive. It is not just "guess" it is rigid mathematical theory. – Euphoric Aug 17 '14 at 15:45
  • @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
  • One could argue that, but that would be wrong. Nor is it correct to say that N = {0, 1, 2, ...}. You could have a program that has undefined behavior for N less than some value, and it would have zero impact on asymptotic running time. The formal definition of asymptotic running time involves a limit as N-> infinity. This makes arguments about N's sign irrelevant. N is always really really big. It doesn't take on any values smaller than we want it to. This is why nobody bothers with the restrictions you're talking about. – Nir Friedman Aug 18 '14 at 14:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.