When i = n , inner query runs for n times ,
now i = n/2 inner query runs n/2 times ,
now i = n/4 inner query runs for n/4 times ,
So the total number of steps the inner query would run is
n + n/2 + n/4 + n/8 + n/16 + ....... for exactly log(n) times .
take n common
n(1+1/2+1/4+1/8+1/16.... ) = n (2 - 1/2^(logn)) = n (2 - 1/n) , lets take n approaches infinity ,
1/n approaches 0.
Therefore , complexity = O(2n) = O(n)