The solution of the problem should be O(n log n)


#1

The solution of the problem should be O(n log n)


#2

but it shows wrong
for ist loop it should run logN times and for inner loop it should run N*logN times


#3

dry run the code.Initially the inner loop will run N times now the value of N gets half then in the second iteration the inner loop will run N/2 times and similarly N/4,N/8…
both the loops will run N+N/2+N/4+N/8… which is a G.P. and the sum is 2*N.