0

I am looking for some help regarding big O notation. The goal is to give the order of growth for the given code fragments.

int sum = 0
for (int k = n; k > 0; k/=2 )
  for (int i = 0; i < k; i++)
    sum++;

For this code fragment I got (N logN). The first for loop is logN and the second for loop is N.

int sum = 0
for (int i = 1; i < n; i *= 2 )
  for (int j = 0; j < i; j++)
    sum++;

I had some trouble on this one. The first for loop is logN, however the second for loop is where I get stuck. The second for loop in dependent on the first for loop. I'm not sure how to show that in big N notation.

int sum = 0
for (int i = 1; i < n; i *= 2 )
  for (int j = 0; j < n; j++)
    sum++;

The first for loop is logN. The second for loop is N. So this is (N)?

I am struggling with this and would appreciate some help. Thank you

1
  • The last example is still N * logN. You have to perform N operations log N times, ergo, you get N * log N. May 4, 2018 at 18:17

1 Answer 1

1
  1. You are correct on the first code fragment: O(n*log n).

  2. In the second code fragment, j loops up to i, which can goes as high as n - 1, so that j for loop is O(n) by itself. But let's examine what happens.

    • n = 16
    • i = 1 The inner loop runs 1 time.
    • i = 2 The inner loop runs 2 times.
    • i = 4 The inner loop runs 4 times.
    • i = 8 The inner loop runs 8 times.

    • n = 17

    • i = 1 The inner loop runs 1 time.
    • i = 2 The inner loop runs 2 times.
    • i = 4 The inner loop runs 4 times.
    • i = 8 The inner loop runs 8 times.
    • i = 16 The inner loop runs 16 times.

The counts of the loops is

1 + 2 + 4 + ... + 2^x = 2^(x+1) - 1

where x is the power of 2 before n. This 2^(x+1) could be as high as 2n, so the overall complexity is O(n), dropping the constant "2".

  1. The third code fragment is similar to the second code fragment; only that j goes all the way to n each time. The complexity here is O(n*log n).
2
  • Wouldn't the second inner run to i-1 each time thereby making it n(n+1)/2? Sorry, not n due to the outer; that would have to be adjusted for the log. May 4, 2018 at 18:21
  • @ChiefTwoPencils That is incorrect, but my original analysis of the second fragment was incorrect too. I've corrected it now.
    – rgettman
    May 4, 2018 at 18:32

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