Time Complexity

Question

Consider the following function

 

for(int n)
{
  for(i = 1; i <= n; i = i*2)
 {
  for(j = 1; j <= i; j = j*2)
   printf(“GATE 2017”);
 }
}

 

Comments

(log n)² ?

Answer 1

two for loops are dependent on each other.

so execute for some value of i and calculate

initially i=1 --------- j=1

i=2 then j=1,2

i=4 then j=1,2,4

i=8 then j=1,2,4,8 times executed.

calculate no of iterations of outer loop=1,2,4,8,...............$2^{k}$

$2^{k}$=n(equate to for loop condition)

k=logn.

and inner for loop execute one more than outer loop

so inner for loop no of iterations=logn+1.

Hence time complexity=logn*(logn+1)=$O((logn)^{2})$

                             

Comments

How does inner loop runs log n + 1 times..?can u explain..?

---

inner loops run log₂ n+1 because i<=n had it been i<n it would just be log₂ n