Why isn't it O(n * log(n))?


#1

What about the outer loop?
The outer loop counts to O(log(n)).
Why are we only considering only the inner loop to calculate the total time complexity which is O(N).

The above problem has a nested loop so shouldn’t we consider both the loops?


#2

total complexity of any nested loop depends upon how many times the inner loop or nested loop has executed.
for this example outer loop i=n, nested loop executes n times
then i=i/2 i.e n/2 loop nested loop executes n/2 times
and similarly till i>0
=>total no. of times nested loop runs is n+n/2+n/4+…+1.