Awesome q2a theme
0 votes
16 views

 

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

$B. O(n^2 logn) $

$C. O(n^2) $

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

ago in Algorithms by (9 points)
edited ago by | 16 views

1 Answer

+2 votes
Best answer
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.

ago by (2.9k points)
edited ago by
0
Thank You @zxy123 I got confused between B and C.

Edit: Option C is $O(n^2)$.
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
8,953 questions
3,113 answers
14,322 comments
95,780 users