Why is 3 n </msup> not in <mi mathvariant="normal">&#x0398;<!-- Θ --> (

Feinsn

Feinsn

Answered question

2022-06-14

Why is 3 n not in Θ ( 2 n )
How is it that 3 n not in Θ ( 2 n ), while l o g 3 n is in Θ ( l o g 2 n )?

Answer & Explanation

Samantha Reid

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 log a ( n ) is Θ ( log b ( n ) ) for any a , b > 1
It suffices to show that 3 n is not O ( 2 n ), i.e., you need to find n such that 3 n > C 2 n , or n ln 3 > n ln 2 + ln C, or n > ln C / ( ln 3 ln 2 ). It's easy to see from the last inequality that there's always such an n for any C.
So while you can say that an algorithm is " log n," and that means pretty much the same thing for any base, you can't say the same thing about "exponential in n." You need to be specific about what base you're referring to. For that reason, many theoretical computer scientists take the notation " 2 O ( n ) " 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 f ( n ) is Θ ( g ( n ) ), you can't expect that f 1 ( n ) is Θ ( g 1 ( n ) ) in general. The result is especially apparent when you try to do this when f and g are logarithmic. You have to deal with C (actually C O and C Ω , since a Θ bound is made up of two other bounds), and once you take exponents the problem pops right out -- that C goes into the exponent and is no longer a simple scalar factor.
aligass2004yi

aligass2004yi

Beginner2022-06-16Added 7 answers

Short answer: The logarithms differ by a constant factor, the exponentials by the factor of ( 3 / 2 ) n 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, 3 n Θ ( 2 n ), but log 3 n = n log 3 = Θ ( log 2 n ) = Θ ( n ).

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?