Big-O complexity of a piece of code

Question

I have a question in algorithm design about complexity. In this question a piece of code is given and I should calculate this code's complexity. The pseudo-code is:

for(i=1;i<=n;i++){     j=i     do{         k=j;         j = j / 2;     }while(k is even); } 

I tried this algorithm for some numbers. and I have gotten different results. for example if n = 6 this algorithm output is like below

i = 1 -> executes 1 time i = 2 -> executes 2 times i = 3 -> executes 1 time i = 4 -> executes 3 times i = 5 -> executes 1 time i = 6 -> executes 2 times 

It doesn't have a regular theme, how should I calculate this?

Answer 1

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

Answer 2

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