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.