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)