Are 2^n and n*2^n in the same time complexity?

Question

Resources I've found on time complexity are unclear about when it is okay to ignore terms in a time complexity equation, specifically with non-polynomial examples.

It's clear to me that given something of the form n² + n + 1, the last two terms are insignificant.

Specifically, given two categorizations, 2ⁿ, and n*(2ⁿ), is the second in the same order as the first? Does the additional n multiplication there matter? Usually resources just say xⁿ is in an exponential and grows much faster... then move on.

I can understand why it wouldn't since 2ⁿ will greatly outpace n, but because they're not being added together, it would matter greatly when comparing the two equations, in fact the difference between them will always be a factor of n, which seems important to say the least.

Answer 1

You will have to go to the formal definition of the big O (O) in order to answer this question.

The definition is that f(x) belongs to O(g(x)) if and only if the limit limsupx → ∞ (f(x)/g(x)) exists i.e. is not infinity. In short this means that there exists a constant M, such that value of f(x)/g(x) is never greater than M.

In the case of your question let f(n) = n ⋅ 2n and let g(n) = 2n. Then f(n)/g(n) is n which will still grow infinitely. Therefore f(n) does not belong to O(g(n)).