Big O (Asymptotic run time), is 3^n = O(2^n)?

Question

I am going through a course that gave an example function of (100033)³ⁿ. It didn't give any explanation other than:

For an exponential function, the coefficient of the exponent is irrelevant to assessing the growth of the function, so the asymptotic run function is usually expressed as 2ⁿ. So, the asymptotic run time function for f(n)=(100033)³ⁿ is 2ⁿ.

And then it gave another example problem of f(n)=3ⁿ+2ⁿ. For this example, it said:

we can ignore 2ⁿ because 3ⁿ is larger and the asymptotic run time is 3ⁿ.

However, after ignoring 2ⁿ we are left with 3ⁿ which is exponential and if I follow the logic of the first example, since 3ⁿ is exponential wouldn't it mean that the asymptotic run time of it is 2ⁿ?

I am a beginner, and this book hasn't explained any of the math behind why any of this works. So I am just applying the logic the book gave me.

Answer 1

The text you quoted makes a wrong claim:

So, the asymptotic run time function for f(n)=(100033)^3n is 2^n

This is false. It is true that the positive coefficient that multiplies can be removed when looking at the asymptotic run time, and so

      () = 100033³ is O(100033)

But one cannot reduce the base of the exponentiation:

      () is not O(2)

Proof that 3 is not O(2)

We can prove this point using the definition of big O.

Let's say () = 3 and we want to see whether () is O(2). Then we should be able to find constants and such that:

      3 ≤ (2) for all >

Let's play with that constraint:

      (3/2) ≤ for all >

Or:

      ≤ log_3/2 for all >

... which is a contradiction. "all > " means we can choose to be some value greater than log_3/2. And that violates the constraint.

The conclusion is that () = 100033³ is not O(2), and the text you quoted is wrong in that claim.

The second quote from the book is a correct statement:

When we have () = 3 + 2, we can drop the second term, as the first term is asymptotically greater than the second, and so we can say () is O(3).

The rules of asymptotic complexity

In summary, if and are positive constants then:

      is O()

But if > 1:

      () is not O()

With concrete values of and (2 and 1.5):

      2^1.5 is O(2)

But:

      3 is not O(2)