Why is
3
n
</msup>
not in
<mi mathvariant="normal">Θ<!-- Θ -->
(
Feinsn
Answered question
2022-06-14
Why is not in How is it that not in , while is in ?
Answer & Explanation
Samantha Reid
Beginner2022-06-15Added 22 answers
You can take any logarithm and convert to a different base simply by multiplying by a constant, so is for any It suffices to show that is not , i.e., you need to find such that , or , or . It's easy to see from the last inequality that there's always such an for any . So while you can say that an algorithm is "," and that means pretty much the same thing for any base, you can't say the same thing about "exponential in ." You need to be specific about what base you're referring to. For that reason, many theoretical computer scientists take the notation "" to be "exponential," because this covers any base. EDIT: I felt like this deserved a response to the "why" part, and I think the answer to that would be that if is , you can't expect that is in general. The result is especially apparent when you try to do this when and are logarithmic. You have to deal with (actually and , since a bound is made up of two other bounds), and once you take exponents the problem pops right out -- that goes into the exponent and is no longer a simple scalar factor.
aligass2004yi
Beginner2022-06-16Added 7 answers
Short answer: The logarithms differ by a constant factor, the exponentials by the factor of which tends to . A slightly more elaborate explanation is that the notation can swallow a constant factor, but not a more ''rapidly increasing'' difference. When you apply logarithms, things generally increase ''slowly'' so the difference is not likely to be so significant. For instance, , but .