Big-O complexity of a piece of code

Question

The upper bound given by the other answers is actually too high. This algorithm has a O(n) runtime, which is a tighter upper bound than O(n*logn).

Proof: Let’s count how many total iterations the inner loop will perform.

The outer loop runs n times. The inner loop runs at least once for each of those.

For even i, the inner loop runs at least twice. This happens n/2 times.
For i divisible by 4, the inner loop runs at least three times. This happens n/4 times.
For i divisible by 8, the inner loop runs at least four times. This happens n/8 times.
…

So the total amount of times the inner loop runs is:

n + n/2 + n/4 + n/8 + n/16 + ... <= 2n

The total amount of inner loop iterations is between n and 2n, i.e. it’s Θ(n).