Time complexity

Question

#include<stdio.h>
int main()
{
int sum =0;
 for(limit=1;limit<=n;limit*=2)
 {
     for(i=0;i<limit;i++)
     {
         for(j=0;j<n;j+=2)
         {
             sum+=j;
         }
         for(j=1;j<n;j*=2)
         {
             sum*=j;
         }
     }
   }
}

Comments

It is O(n²) @Ashwin please share your approach

---

Outer loop (limit) runs for $1,2,4,...2^k$

Inner loop i depends on limit. and j runs for either $n/2$ or $logn$ we will take $n/2$

Now when limit = 1, i runs for 1 time and hence j = n/2

Now when limit = 2,  i runs for 2 times and hence j = 2*n/2

Now when limit = 4,  i runs for 4 times and hence j = 4*n/2

 

Hence generalizing, $\frac{n}{2} [1+2+4+8...2^k]$ where $k = logn$

Hence $\frac{n}{2}(2^k -1) = O(n^2)$

---

O ( n*n)??

Answer 1

The outer loop of limit will run will run for _Logn 

It contain one inner loop of ith loop

 ith loop will also run for logn times

 Jth loop runs for n/2 times

And next jth loop will run for logn time

Hence th total complexity for the ith loop becomes

Logn(n/2+logn)=nlogn+(logn)^2

For the outer loop

The total complexoty will become

Logn(nlogn+(logn)^2)

Making the overall complexity=bigoh(n(logn)^2)

#please correct if i m wrong