made easy test series

Question

time complexity of the program is?

Comments

ans O(n^2)

---

Is it O(n²) ?

---

Inner loop runs for (n/2 + logn) times hence bigger is n we have to take that only.

Outer loop runs as,

bound =1 , inner = 1*n/2

bound = 2, inner = 2*n/2

bound = 4, inner = 4*n/2

..

..

bound = 2^k , inner = 2^k*n/2 (n = 2^k) hence k = logn

now by adding up it will give,

1*n/2 + 2*n/2 + 4*n/2 .... 2^k *n/2

n/2 [ 1+2+4 ... 2^k]

n/2 * 2n

O(n²)