# Run time for a specific loop confusion

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$$?

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.
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.
• 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. – Simon Garfe Jul 21 at 16:15