Big-O complexity of a piece of code

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).

You always assume you get the worst scenario in each level.
now, you iterate over an array with N elements, so we start with O(N) already.
now let's say your i is always equals to X and X is always even (remember, worst case every time).
how many times you need to divide X by 2 to get 1 ? (which is the only condition for even numbers to stop the division, when they reach 1).
in other words, we need to solve the equation X/2^k = 1 which is X=2^k and k=log<2>(X) this makes our algorithm take O(n log<2>(X)) steps, which can easly be written as O(nlog(n))

For such loop, we cannot separate count of inner loop and outer loop -> variables are tighted!

We thus have to count all steps.

In fact, for each iteration of outer loop (on i), we will have

1 + v_2(i) steps

where v_2 is the 2-adic valuation (see for example : http://planetmath.org/padicvaluation) which corresponds to the power of 2 in the decomposition in prime factor of i.

So if we add steps for all i we get a total number of steps of :

n_steps = \sum_{i=1}^{n} (1 + v_2(i)) 
        = n + v_2(n!)    // since v_2(i) + v_2(j) = v_2(i*j)
        = 2n - s_2(n)    // from Legendre formula (see http://en.wikipedia.org/wiki/Legendre%27s_formula with `p = 2`)

We then see that the number of steps is exactly :

n_steps = 2n - s_2(n)

As s_2(n) is the sum of the digits of n in base 2, it is negligible (at most log_2(n) since digit in base 2 is 0 or 1 and as there is at most log_2(n) digits) compared to n.

So the complexity of your algorithm is equivalent to n:

n_steps = O(n)

which is not the O(nlog(n)) stated in many other solutions but a smaller quantity!