complexity for a nested loop with varying internal loop

Question

Very similar complexity examples. I am trying to understand as to how these questions vary. Exam coming up tomorrow :( Any shortcuts for find the complexities here.

CASE 1:

void doit(int N) { 
   while (N) {
      for (int j = 0; j < N; j += 1) {}
   N = N / 2;   
   }
}

CASE 2:

void doit(int N) { 
   while (N) {
      for (int j = 0; j < N; j *= 4) {}
   N = N / 2;   
   }
}

CASE 3:

void doit(int N) { 
   while (N) {
      for (int j = 0; j < N; j *= 2) {}
   N = N / 2;   
   }
}

Thank you so much!

the answer to number one is O(N)...but i am not sure how to solve it mathematically, is someone can point me how to do that in the answer it would be great. If you look at the first answer here, Amit has proved it mathematically, something similar would be great: stackoverflow.com/questions/13818794/… — Mathew Kurian
– Mathew Kurian, Commented Dec 12, 2012 at 5:56

NickO · Accepted Answer · 2012-12-12 06:27:22Z

4

void doit(int N) { 
   while (N) {
     for (int j = 0; j < N; j += 1) {}
   N = N / 2;   
   }
}

To find the O() of this, notice that we are dividing N by 2 each iteration. So, (not to insult your intelligence, but for completeness) the final non-zero iteration through the loop we will have N=1. The time before that we will have N=a(2), then before that N=a(4)... where 0< a < N (note those are non-inclusive bounds). So, this loop will execute a total of log(N) times, meaning the first iteration we see that N=a2^(floor(log(N))).

Why do we care about that? Well, it's a geometric series which has a nice closed form:

Sum = \sum_{k=0}^{\log(N)} a2^k = a*\frac{1-2^{\log N +1}}{1-2} = 2aN-a = O(N).

If someone can figure out how to get that latexy notation to display correctly for me I would really appreciate it.

edited Dec 12, 2012 at 6:27

answered Dec 12, 2012 at 6:08

NickO

7411 gold badge7 silver badges20 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

amit · Accepted Answer · 2012-12-12 07:21:03Z

You already have the answer to number 1 - O(n), as given by @NickO, here is an alternative explanation.

Denote the number of outer repeats of inner loop by T(N), and let the number of outer loops be h. Note that h = log_2(N)

T(N) = N + N/2 + ... + N / (2^i) + ... + 2 + 1
     < 2N (sum of geometric series)
     in O(N)

Number 3: is O((logN)^2)

Denote the number of outer repeats of inner loop by T(N), and let the number of outer loops be h. Note that h = log_2(N)

T(N) = log(N) + log(N/2) + log(N/4) + ... + log(1)   (because log(a*b) = log(a) + log(b)
     = log(N * (N/2) * (N/4) * ... * 1)
     = log(N^h * (1 * 1/2 * 1/4 * .... * 1/N))
     = log(N^h) + log(1 * 1/2 * 1/4 * .... * 1/N)    (because log(a*b) = log(a) + log(b))
     < log(N^h) + log(1)
     = log(N^h)                                      (log(1) = 0)
     = h * log(N)                                    (log(a^b) = b*log(a))
     = (log(N))^2                                    (because h=log_2(N))

Number 2 is almost identical to number 3.

(In 2,3: assuming j starts from 1, not from 0, if this is not the case @WhozCraig giving the reason why it never breaks)

Collectives™ on Stack Overflow

complexity for a nested loop with varying internal loop

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related