Made Easy Test Series

Question

 

$A. O(n (logn)^2) $

$B. O(n^2 logn) $

$C. O(n^2) $

$D. O(n log(log(n)))$

Answer 1

main ()
{
    int s = 0; // O(1)
    for (int b = 1; b <= n; b *= 2) // loop 1
    {
        for (int i = 0; i < b; i++) // loop 2
        {
            for (int j = 0; j < n; j += 2) // O(n/2)
            {
                s = s + j; //O(1)
            }
            for (int j = 1; j < n; j *= 2) // O(log(n))
            {
                s = s*j; //O(1)
            }
        }
    }
}

We have to resolve the first two loop together as they are dependent.

When b = 1, loop 2 will run 1 time.

When b = 2, loop 2 will run 2 times.

.

.

.

When b = n, loop 2 will run n times.

So total times loop 1 and loop 2 run will be $$S = 1 + 2 + 4 + 8 + … n$$

This is a GP with $log_2(n) + 1$ terms, so sum will be $$\frac{a(r^{n-1})}{r-1} = \frac{1(2^{log_2(n) + 1} – 1)}{2-1} = 2n – 1 = O(n)$$

Time complexity = $O(n)\times (O(n/2) + O(log(n))) = O(n^2)$ 

Best suited option will be C.

Comments

Thank You @zxy123 I got confused between B and C.

Edit: Option C is $O(n^2)$.