Are 2^n and n*2^n in the same time complexity?
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 n2 + n + 1, the last two terms are insignificant.
Specifically, given two categorizations, 2n, and n*(2n), is the second in the same order as the first? Does the additional n multiplication there matter? Usually resources just say xn is in an exponential and grows much faster... then move on.
I can understand why it wouldn't since 2n 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.
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 ie 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)) .
A quick way to see that n⋅2ⁿ is bigger is to make a change of variable. Let m = 2ⁿ . Then n⋅2ⁿ = ( log₂m )⋅m (taking the base-2 logarithm on both sides of m = 2ⁿ gives n = log₂m ), and you can easily show that m log₂m grows faster than m .
I agree that n⋅2ⁿ is not in O(2ⁿ) , but I thought it should be more explicit since the limit superior usage doesn't always hold.
By the formal definition of Big-O: f(n) is in O(g(n)) if there exist constants c > 0 and n₀ ≥ 0 such that for all n ≥ n₀ we have f(n) ≤ c⋅g(n) . It can easily be shown that no such constants exist for f(n) = n⋅2ⁿ and g(n) = 2ⁿ . However, it can be shown that g(n) is in O(f(n)) .
In other words, n⋅2ⁿ is lower bounded by 2ⁿ . This is intuitive. Although they are both exponential and thus are equally unlikely to be used in most practical circumstances, we cannot say they are of the same order because 2ⁿ necessarily grows slower than n⋅2ⁿ .