See here we analyse like this..Think it the reverse way i.e. i begins from n , divided by 2 in each iteration and finally i = 1..No adjustment needed for 'j'..
So no of times j runs when i = n ==> n times
no of times j runs when i = n / 2 ==> n / 2 times
no of times j runs when i = n / 2 ==> n / 4 times
.....
no of times j runs when i = 1 ==> 1 time
So T(n) = No of times j runs here
= n [ 1 + 1/2 + 1/4 + 1/8 ..........+ 1/n ]
= kn [ As common ratio is less than 1 hence a decreasing G.P. hence sum will be some constant 'k' ]
= O(n)
Hence O(n) is correct answer..
