0
$\begingroup$

I need to find out number of iterations this while loop will perform before terminating.

I have calculated log(1000/n) and complexity is logb(n), is it correct?

while n <100,000
n←n×b
endwhile
$\endgroup$
  • $\begingroup$ What is the initial value of $n$ before the start of the loop? Is it $1$? $\endgroup$ – John Omielan Feb 11 at 1:43
  • $\begingroup$ Yeah you can consider that $\endgroup$ – June Feb 11 at 1:48
  • 1
    $\begingroup$ Since the value of $n$ changes during the loop, it doesn't make sense for it to show up in the formula for the complexity of the entire loop. It might make sense for the starting value of $n$ to be in the formula if the loop is allowed to start from different initial values, but you would have to give that number its own name. $\endgroup$ – David K Feb 11 at 2:28
  • $\begingroup$ By the way, a step-by-step explanation of your reasoning could help. To fix the math notation, start here: math.stackexchange.com/help/notation $\endgroup$ – David K Feb 11 at 2:47
0
$\begingroup$

You need to play a bit and see what values does $n$ takes?

$$n = 1 [=b^0]$$ $$n = b [=b^1]$$ $$n = b^2$$ $$\vdots$$ $$n = b^k [= 100, 000]$$

So $k = \log_b 100,000 = O(1)$ for reasonable $b$ (i.e. $b > 1$).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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