CODEWITHSUNDEEP
algorithmtime-complexitybig-o
WWBM
WWBM

Reputation: 25

Time complexity(nested loops)

How do you work out the time complexity of this?

int count=0;

for (int i=1 ; i < n; i*=4)

     for (int j=1;j<=n;j++)

              count++;

Upvotes: 0

Views: 123

Answers (1)

amit
amit

Reputation: 178411

tl;dr: Complexity of the posted code is: O(nlogn)

Let's analyze it from the inside out. The inner loop repeats itself exactly n times for each value of i.

The outer loop repeats itself while i < n, and i is multiplies by 4 each time. This means, after the first iteration, i=1, then i=4, i=16, i=64, .... and after the k'th iteration i = 4^(k-1).
This means, you stop when:

i >= n
4^(k-1) >= n
log_4(4^(k-1)) >= log_4(n)
k-1 >= log_4(n).

This means the outer loop will repeat log_4(n) + 1.

Summing it all together gives you n*(log_4(n)+1) times the inner loop repeats, which is in O(nlogn)

Upvotes: 6

Related Questions