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

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

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

Awesome q2a theme

+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.

8,953 questions

3,113 answers

14,322 comments

95,780 users