Time Complexity of the given code ?

Question

#include <stdio.h>

int main(void) {
	for(i=1;i<=n;i*=2)
	{
	    for(j=0;j<=i;j++)
	    {
	        for(k=0;k<=n;k++)
            {
                 ..... O(1)....;
            }
	    }
	}
	return 0;
}

---

What is the time complexity of given code ?

Comments

n(logn)² ??

---

Sorry !!

---

It should be n^2 logn.

---

NO !!

---

it's $O(n^2)$ and I hate No's

---

@Kapil, in the second loop does the question has  j<i or of j<=i ?

---

nlogn

---

yes, It should be O(n²).

T(n)= (1+ 2 + 4 + 8 + 16 + 32 + ..... + log(n) term. )  * O(n).

      = O(n) * O(n) = O(n²) .. 

---

Yes it should be n^2. Earlier I made a mistake forgot that in order to examine middle loop aggregate analysis was done.

---

inner for loop for index k is running n times

for loop with index j is running i+1 times

and outer for loop is running (logn + 1) times if we consider n as power of 2

that means for loop with index j is running for [ (1+1) + (2+1) + (4+1) + ....... + (2^logn+1) ] times

so the sum will be = [ 1 + 2 + 4 + ..... + 2^logn ] + [ 1 + 1 + 1 + .... (logn+1) times ]

= 2^logn+1 - 1 + logn + 1

= O(n + logn)

now multiplying with O(n) becoz innermost query runs for n times

= O(n²+nlogn) = O(n²)

Answer 1

Modifying the condition in second loop. Changing from j<=i to j<i. Reason: Asymptotically it wont make a difference.

Total T(n) : OuterLoop * Middle * Innermost

Outer loop Executes: logn times

Innermost Executes: n times

Aggregate Analysis of Middle loop :
Lets examine the middle one. Since it is not trivial to identify. Lets take an example.
Assume n=8

When i =1 j will execute for 1 time ( iterNo = 0 )

When i =2 j will execute for 2 time ( iterNo = 0,1 )

When i =4 j will execute for 4 time ( iterNo = 0,1,2,3 )

When i =8 j will execute for 8 time ( iterNo = 0,1,2,3,5,4,6,7 )

Thus middle loop is executing sum of GP with last term = n.

Height of this GP will be 2^h = n

Hence h =   log n

Thus Sum of GP =  ( 2^(logn + 1) - 1)/ ( 2 -1 )

Simplifying gives n

Hence total T(n) =  n * n

= n^2