Why the confusion?


Theta notation means that the function is bounded from above and below. In short, we want the exact complexity of this algorithm.

Outer Loop analysis :
i = n/2 to n with increment by 1. Hence this iterates just n/2 times.

Inner Loop analysis :
j = 2 to n but with multiplication by 2.

Let’s approach this mathematically

2^k = n this means that j = 2 after multiplying k times will reach n.
For example, if n = 8 then the inner loop will iterate 3 times. If n = 16 inner loop will iterate 4 times and so on. Basically, it’s log.

What is the value of k? Just take log

k = log base 2 n

hence inner loop will iterate logn times

Total complexity n/2logn = nlogn as we don’t care about constants in asymptotic notations.

Hope it helps.


thanks for contributing!