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

$O(nlogn)$ ?

---

@srestha

What you want to ask I'm not getting. Please explain a little bit.

---

time complexity?

no still ans not matching

Plz explain

---

because $2^0$ $2^2$ $2^3$ $2^4$ $2^5$ $2^6$ .......... $2^k$--> here the loop is running k times

$2^k$ <= n

=>k <= $logn$

As the loop is running K times (i.e. logn) times and 

for(j=0;j<n;j+=2)
{
   sum+=j;
} // takes O(n/2) --> this is the inner loop

TC = logn * n==>$O(n logn)$

---

( 2n - 1 )* (log n + n/ 2) ???

---

Both are same right( your first and previous response ) kumar.dilip

---

Yes, but I wanted to give the answer according to the question, that's why I did this.

---

( 2(log n + 1) - 1 )* (log n + n/ 2)

why '+' will not be '*' ?

---

answer is correct or not ??

---

no ans something else

but I got like this

---

i am getting O(n²)

---

Is answer O(log^3). If right I will the explanation.

---

Nope.

Given ANS is n^2.

---

Okk ..I understood my mistake .

The first loop will run for logn times.

Loop inside the 2nd loop that is variable j will run for n times and last loop will run for logn time. As O(logn+n)=O(n). It will be n. Now

loop will run like this n+2*n+4*n+8*n....  logn times which forms a GP .Taking n common we get n*(1+2+4..)

So by formula of sum of gp

n*(2^logn-1). It will be n^2.

---

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