0
$\begingroup$

This question already has an answer here:

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)
|cite|improve this question
$\endgroup$

marked as duplicate by Raphael♦ Aug 23 '18 at 22:42

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Welcome to Computer Science! What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? $\endgroup$ – Raphael♦ Aug 23 '18 at 22:43
  • $\begingroup$ @Raphael I updated the post with what i tried out and the point where i get stuck and get all kinds of mistakes $\endgroup$ – Rares Andrei Aug 24 '18 at 10:17
  • $\begingroup$ "We do not want to just hand you the solution" I don't wish for the solution, I posted in hope I get a full resolved problem so I can see and understand the solving algorithm $\endgroup$ – Rares Andrei Aug 24 '18 at 10:35
  • $\begingroup$ That's what we mean by "solution", yes. The end result "O(...)" is never a "solution" in exercise problem terms. $\endgroup$ – Raphael♦ Aug 24 '18 at 14:45
0
$\begingroup$

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

|cite|improve this answer
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.