16 views

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

$B. O(n^2 logn)$

$C. O(n^2)$

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

ago
edited ago | 16 views

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)$.