recategorized by
1,017 views
3 votes
3 votes
#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 ?

recategorized by

1 Answer

2 votes
2 votes

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 

edited by

Related questions

0 votes
0 votes
1 answer
1
0 votes
0 votes
2 answers
2
omveer asked Sep 5, 2016
460 views
While(n>1){n=n/20;n=n/10;}Find time complexity.
0 votes
0 votes
1 answer
3
LavTheRawkstar asked Jan 12, 2017
806 views
INSERTION-SORT (A, n) ⊳ A[1 . . n]for (j ← 2 to len(A) ){key ← A[ j];i ← j – 1 ; while (i 0 and A[i] key) { A[...
0 votes
0 votes
0 answers
4