# Complexity of a while loop that divides by parameter by three each iteration

I've learned that a while loop such as

int i = 100;
while (i >= 1){
...
///Stuff
i = i/2
}


will run in logarithmic time, specifically, O(logn), since it keeps dividing in half each time (like a binary search).

However, what if my while loop looks like this

 int i = 100;
while (i >= 1){
...
///Stuff
i = i/3
}


Is the complexity still O(logn)?

Can someone explain yes/no and why?

• Yes, it will be $O(\log n)$, indeed it will be $O(\log_3 n)$, which is $O(\log n)$. Recall that $\log_a n = c \log_b n$ for some constant $c$. – Pål GD Mar 8 '13 at 19:46
• ...where $c=\log_a b$. In fact, the time will also be $O(\log_{42} n)$, because the $O(\cdot)$ notation swallows the constant $\log_3 42$. – JeffE Mar 8 '13 at 19:51
• Pardon my math ignorance, but why is $log_an=clog_bn$ for some constant c? I mean, I just tested it with an example and it appears right, but I can't see why – CodyBugstein Mar 8 '13 at 19:53
• See also here and here and here. – Raphael Mar 8 '13 at 20:47
• $n = b^{log_b n} = (a^{\log_a b})^{\log_b n} = a^{(\log_a b)(\log_b n)}$ – Sasho Nikolov Mar 9 '13 at 18:20

Hint: The number of times the loop is run, assuming it starts at $n$ and divides by $b$ each time, is exactly $\lfloor \log_b n \rfloor + 1$.