-2
$\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$

migrated from cstheory.stackexchange.com Mar 8 '13 at 19:38

This question came from our site for theoretical computer scientists and researchers in related fields.

  • 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 Mar 8 '13 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 Mar 8 '13 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$ – CodyBugstein Mar 8 '13 at 19:53
  • $\begingroup$ See also here and here and here. $\endgroup$ – Raphael Mar 8 '13 at 20:47
  • $\begingroup$ $n = b^{log_b n} = (a^{\log_a b})^{\log_b n} = a^{(\log_a b)(\log_b n)}$ $\endgroup$ – Sasho Nikolov Mar 9 '13 at 18:20
1
$\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, privacy policy and cookie policy

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