Programming (Time Complexity)

Question

What will be time complexity:

main()
{
    int sum=0;
    for(int bound=1;bound<=n;bound*=2)
    {
        for(int i=0;i<bound;i++)
        {
            for(j=0;j<n;j+=2)
            {
                sum+=j;
            }
            for(int j=1;j<n;j*=2)
            {
                sum*=j;
            }
        }
    }
}

I think every for loop is participating to find T.C.

something*2 means why will it run upto $log n$ and not upto $\frac{n}{2}$

Comments

Ashish Roy 1

Please don't post the answer to early.First discuss

---

......

---

O($n^{2}$) should be correct.

Answer 1

for(int bound=1;bound<=n;bound*=2)
{
     for(int i=0;i<bound;i++)
     {
         for(j=0;j<n;j+=2) ====> O(n/2)
         {
             sum+=j;
         }
         for(int j=1;j<n;j*=2)===> O(logn)
         {
           sum*=j;
         }
     }
}

 

O($\frac{n}{2}$) + O(log₂n) = O(n) + O(log₂n) = O(n)

 

for(int bound=1;bound<=n;bound*=2)
{
     for(int i=0;i<bound;i++)
     {
         O(n)
     }
}

 

let n= 2^k, then

bound = 1 ===> i runs one time i.e., i=0

bound = 2¹ ===> i runs 2¹ times i.e., i=0,i=1

bound = 2² ===> i runs 2² times i.e., i=0,i=1,i=2,i=3

......

bound = 2^k ===> i runs 2^k times i.e., i=0,i=1,i=2,....i=(n-1)

 

===> total times = 2⁰ + 2¹ + 2² + ...... + 2^k = 2^(k+1) - 1 = 2.2^k - 1 = 2 n - 1. ===> O(n)

But each time it runs O(n) times

∴ Total Time Complexity = O(n) . O(n) = O(n²)

Comments

$2^{k}=n$

$\Rightarrow k=log n$

and $2^{logn}=n$

right?

---

Yes mam

---

if the i loop will run like (i=0;i<=n;i++) then overall TC will be $n^2logn$ ?

---

yes