Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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.

like image 488
matty-d Avatar asked Feb 13 '14 20:02

matty-d


People also ask

Is O (n/2) a valid time complexity?

Technically, yes, O ( n / 2) is a “valid” time complexity. It is the set of functions f ( n) such that there exist positive constants c and n 0 such that 0 ≤ f ( n) ≤ c n / 2 for all n ≥ n 0.

Is N⋅2ⁿ the same group of complexity with exponential growth?

But n⋅2ⁿ grows is still only exponential. When we talk about algorithms, we often say that time complexity grows is exponential. So, we consider to be 2ⁿ, 3ⁿ, eⁿ, 2.000001ⁿ, or our n⋅2ⁿ to be same group of complexity with exponential grows.

Is 2^n the same complexity as 4^N?

Yes: one way to see this is to notice 4^n = 2^ (2n). So 2^n is the same complexity as 4^n (exponential) because n and 2n are the same complexity (linear).

When do two algorithms have the same O complexity but different speeds?

If algorithm A is a billion times slower than algorithm B, then they have same O complexity, as long as that difference doesn't grow when n grows arbitrarily large. Let's assume a constant factor of 1000000 to illustrate the concept - it's a million times larger than neccessary, but that illustrates the point that they're considered irrelevant.


2 Answers

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)).

like image 78
Ivaylo Strandjev Avatar answered Dec 01 '22 14:12

Ivaylo Strandjev


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.

like image 20
chepner Avatar answered Dec 01 '22 12:12

chepner