Made Easy test full length

Question

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

options are : a)O(nlogn)

b)O(n^2 logn)

c)O((logn)^2)

d)O(n(logn)^2)

The answer given is B

BUT Shouldn't the answer be D ? I was thinking that if the outer loop runs logn times...the middle loop and outer loops together should run (logn *(logn+1)) times...Am I wrong ?

Also could someone please help me understand the difference between log(logn), log^2n(log square n) and (logn)^2 ?

Answer 1

The complexity should be

$T(n) = \sum_{bound = 1}^n \text{bound} \times \frac{n}{2} \\=1.\frac{n}{2} + 2.\frac{n}{2} + 4. \frac{n}{2} + \dots + n. \frac{n}{2} \\= \frac{n}{2} . \left[1 + 2 + 4 + \dots + n\right] \\= \frac{n}{2} 2^{\lg n -1} = \Theta(n^2)$.

If two sibling loops are there we need to only consider the most critical one for time complexity. But here the middle loop is dependent on outer loop iteration variable and so we cannot find its complexity separate and multiply.

Comments

You are right sir..thank you :)

i made a foolish mistake(thinking the secong outer loop would run upto a maximum of logn....but it would repeat upto n times).Your answer is perfect. :)

---

Just one more doubt sir: is log^2n (log square n) and log(logn) same. what about (logn)^2 {logn whole square}

---

$\log n \times \log n = \log^2 n. \log \log n$ is different. It is applying $\log$ two times.

Answer 2

This is the solution given