-1
$\begingroup$

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?

$\endgroup$
5
  • 3
    $\begingroup$ 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$. $\endgroup$
    – Pål GD
    Commented Mar 8, 2013 at 19:46
  • 1
    $\begingroup$ ...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$. $\endgroup$
    – JeffE
    Commented Mar 8, 2013 at 19:51
  • $\begingroup$ 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 $\endgroup$ Commented Mar 8, 2013 at 19:53
  • $\begingroup$ See also here and here and here. $\endgroup$
    – Raphael
    Commented Mar 8, 2013 at 20:47
  • $\begingroup$ $n = b^{log_b n} = (a^{\log_a b})^{\log_b n} = a^{(\log_a b)(\log_b n)}$ $\endgroup$ Commented Mar 9, 2013 at 18:20

1 Answer 1

3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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