CSC300: What's the result? [9/13] Previous pageContentsNext page

01
02
03
04
05
    for (long i = N; i > 0; i = i/2) {
      for (long j = N; j > i; j = j-1) {
        result = result+1;
      }
    }

Choices:

  1. independent of N -- constant
  2. ~ lg N -- logarithmic
  3. ~ (lg N)^2 -- log squared
  4. ~ N -- linear
  5. ~ 2N -- linear
  6. ~ N(lg N) -- linearithmic
  7. ~ (N^2)/2 -- quadratic
  8. ~ N^2 -- quadratic
  9. ~ N^3 -- cubic
  10. ~ 2^N -- exponential

Previous pageContentsNext page