1
$\begingroup$

I have a loop: for(int i = 1; i < N; i*=5) {...}

where {...} is some statement.

I'm trying to understand its run time. So, far I know that:

  • We start with $i = 1$

  • We finish when $i > n$

  • $i$ is incremented by being multiplied by 5.

So, would the run-time be $\log_5(n-1)$? The reason I'm not sure it's because I thought when analyzing algorithms we had to use base 2 log functions. If the latter is the case how would I got about converting $\log_5$ to $\log_2$?

$\endgroup$
3
$\begingroup$

A basic result in elementary arithmetic states that $$ \log_a n = \log_a b \cdot \log_b n. $$ Indeed, on the one hand, $a^{\log_a n}$ by definition. On the other hand, $$ a^{\log_a b \cdot \log_b n} = (a^{\log_a b})^{\log_b n} = b^{\log_b n} = n. $$ Similarly, $$ \log_b n = \log_b a \cdot \log_a n. $$ This shows that every two logarithms only differ by a constant multiple. Since big O notation discounts constant factors, it doesn't matter which logarithm you use (unless it's in the exponent). For example, a function is $O(\log_a n)$ iff it is $O(\log_b n)$. For this reason we usually don't bother writing the basis of a logarithm in big O notation.

$\endgroup$
1
$\begingroup$

I don't know what you intended to write, but your loop runs in constant time if N <= 0, and will never finish if N > 0.

If you start with i = 0, and multiply i by 5, guess what: It's still 0. I really can't see how you get to $i^5$. After k iterations, the initial value of i is replaced with $i * 5^k$; since the initial value is 0, it stays 0, and the loop never exits if N > 0.

If you started with i = 1, it would be extremely unlikely that you would ever get i = N-1. For example, the loop will exit with i = 3,125 with the last iteration i = 625 for all 625 < N ≤ 3,125. Only when N is one larger than a power of 5 will i ever equal N-1 (if we start with i = 1).

$\endgroup$
  • $\begingroup$ I meant for i to start with one and you're right with i finishing in n-1 is highly unlikely. I will edit my question appropriately. $\endgroup$ – Simon Garfe Jul 21 at 16:15

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.