Exponential nested Loop Big O complexity calculation [duplicate]

Question

This question already has an answer here:

• Is there a system behind the magic of algorithm analysis? 3 answers

Can I get a bit of help over here, I can't seem to get to a finish point with this code complexity. I have trouble with making notations, exponential ones in particular..... I spent hours with this particular piece of code to get BIG O but i can't mathematically..... I'm a newbie.

I tried to logarithmate the whole thing like: j= n, n^(1/2), n^(1/4), ........, 2 then:

j= log (2,n), log(2, n^(1/2)), ..... log (2, (n^(1/2))^K) need to find out K from this notation

If i try to sum them up: log(2,n) + 1/2*log(2,n) + 1/4*log(2,n) + ..... + (1/2)^K * log(2,n)

then:

log(2,n) * [1/2 + 1/4 + ....... + (1/2)^K] The number of terms this sum has should give me the number of steps for j I can't proceed to i without it but i get stuck right there at that sum at this point and i get lost from here.....

I also made a piece of code to count the steps and have a better view here are the results for

n = 1000

for j: 1000 i: 1000, 500, 250, 125, 62, 31, 15, 7, 3, 1, steps: 10

for j: 31 i: 31, 15, 7, 3, 1, steps: 5

for j: 5 i: 5, 2, 1, steps: 3

for j: 2 i: 2, 1, steps: 2

n = 65

for j: 65 i: 65, 32, 16, 8, 4, 2, 1, steps: 7

for j: 8 i: 8, 4, 2, 1, steps: 4

for j: 2 i: 2, 1, steps: 2

for (int j=n; j>1; j=sqrt(j))
       for (int i=j; i>0; i/=2)
             k++; // O(1)

Answer 1

Let n = 65,536 and write down what exactly happens. That should be enough to figure it out.