CODEWITHSUNDEEP
calgorithmcomplexity-theorybig-o
Mathew Kurian
Mathew Kurian

Reputation: 6039

complexity for a nested loop with varying internal loop

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!

Upvotes: 1

Views: 183

Answers (2)

amit
amit

Reputation: 178431

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)

Upvotes: 3

NickO
NickO

Reputation: 741

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.

Upvotes: 4

Related Questions