I'm not sure we should answer homework questions here, but this one is cute so... At first sight it seems like O(N log(N)) at worst, because the outer loop doe

I'm not sure we should answer homework questions here, but this one is cute so... At first sight it seems like O(N log(N)) at worst, because the outer loop does log(N) iterations. But you can actually get tighter. The number of inner loop iterations is N + (N/2) + (N/4) + ... + 1 <= N + (N/2) + (N/4) + ... = N (1 + 1/2 + 1/4 + ...) = N 2 so we can write O(2N).