Whats the dominant term in 2^n or n^2 for big O notation

Question

I have been looking at Big O notation and have come across an operational count 2^n+n^2. I understand the practice of big O notation is to remove the constants and the low order terms, however I cant figure out which one to make O(n). I think it may be 2^n but have had no luck finding anything to suggest this.

Hyperthyroidism

Answer 1

Look at the growth factor over time. For the first eight values of n, O(n^2) works out to:

0, 1, 4, 9, 16, 25, 36, 49...

O(2^n) produces powers of two:

1, 2, 4, 8, 16, 32, 64, 128...

It should be fairly obvious which one is growing faster.

Note that the general rule applies even with different bases and exponents. O(1.1^n) may have initially lower work than O(n^10) for smaller n, but all exponential growth with an exponent greater than 1 will eventually outpace fixed exponent polynomial growth as n approaches infinity.

Unrestraint

2 is not a square number. – Outlive

@aschepler: headdesk. Sorry about that; fixed. – Unrestraint

Thanks for that, it seems obvious now. – Hyperthyroidism

Since when do we call it geometric growth if the exponent is fixed? I only know this as polynomial growth. – Citation

@HermannDöppes: Okay, apparently I really need to get more sleep. Also fixed. – Unrestraint

Answer 2

By L'Hopital's rule:

lim_{n -> infinity} (n^2 / 2^n )

= 1/log(2) lim_{n -> infinity} (2n / 2^n)

= 1/log(2)^2 lim_{n -> infinity} (2 / 2^n)

= 0

We have n^2 = o(2^n) which implies n^2 = O(2^n).

If this proof doesn't make sense: By definition, f(n) = O(g(n) if and only if f(n) is bounded within some constant multiple of g(n) after n grows past some constant. And a way to think of f(n) = o(g(n)) is that as n grows to infinity, g(n) will continue to outgrow f(n) faster. In other words:

1. f(n) = o(g(n)) if and only if the limit f(n)/g(n) becomes zero as n goes to infinity.

2. o(g(n) is a strictly stronger condition that f(n) = O(g(n)).

Alternatively, you just need to use the definition directly: Find some a and b such that n^2 <= a | 2^n | for all n >= b, which is simple algebraic manipulation.

Galliard

It's funny when things like "2^n is dominant, because it grows faster for larger n" get upvotes and actual proofs get ignored. – Respectful

@Katie. I like your proof, except for one thing. If the OP is able to understand this, I feel like he/she wouldn't be asking for this. – Crescantia

@ndn :) such is life. – Galliard

@Crescantia I know right... unfortunately I've come to realize people misuse Landau notation because they've never spent time to understand the subtleties of the definition and end up further in their academic or professional lives mistaking boundedness with asymptotic growth and vice versa. Or they become very surprised to hear that O(n) linear scan can be faster than O(log(n)) binary search and think that the notation fails because of practical matters like cache lines - it is true that cache hierarchy is at play here, but this doesn't imply failure of the notation. – Galliard

Answer 3

I really like @ShadowRanger's answer to your question. But, I want to show one more view of the question.

If you take a look at this graph, the green portion is 2^n with the red n^2. If you can see, at the beginning, the line n^2 grows faster than 2^n, but as you get bigger, the lines cross and 2^n starts to become bigger, faster.

So, as n-->∞ (as n gets very big), 2^n is bigger than n^2.

Crescantia

Answer 4

2^n is dominant, because it grows faster for larger n.

Buffalo

Answer 5

---

---

---

TIL: writing math in SO is pain in the bottoms!

Respectful

how did 2^(n0+1) become 2(n0^2) in the next step? – Leverage

@RohanDevaki, oops... I have no idea how nobody noticed up until now. I will fix it later. Thanks! – Respectful

your solution is very difficult to understand : \ – Leverage

@RohanDevaki, I would have written it a bit different if it was on paper/whiteboard, but in general it's standard notation. Let me know where you got stuck so I can attempt to explain it better. – Respectful

Answer 6

Reposting my answer here from reddit, where someone asked about this.

You have to start with the definitions. O(n^2) < O(2^n) means there is some N such that for all n > N, a*n^2 < b*2^n, for any choice of positive constants a and b.

In other words, if you increase n enough, then a*n^2 < b*2^n regardless of what positive values a and b are. Remember, this is what the statement O(n^2) < O(2^n) means. The proof is to be shown. Let a, b be positive real numbers. Can we find N such that for all n > N, a*n^2 < b*2^n?

Well, if you solve a*N'^2 = b*2^N' for N', you would be able to find the crossing point between the two functions, and then you can just choose N to be a number greater than N'. From that, you can use induction to prove that any n > N implies a*n^2 < b*2^n.

This approach is hard because it's not easy to solve: b*2^N' - a*N'^2 = 0 for N' (but can be done apparently, you can check Wolfram Alpha for the solution.)

There is another way, which is to use L'Hopital's rule. First, we rewrite the problem to be: Can we find N such that for all n > N, 1 < (b*2^n)/(a*n^2)?

Let's call the right hand side, g(n), so we are now looking for an N such that for all n > N, g(n) > 1.

We can do this by using the definition of limit. Let L be the limit of g(n) as n approaches infinity. If the limit L is infinity, then that means by definition, for any lower threshold M, there exists an N'' such that if n > N'' then g(n) > M. (See the definition here: https://en.wikipedia.org/wiki/Limit_(mathematics)#Infinity_as_a_limit)

In our case, our choice for M is 1. So, if we prove limit L is infinity, then we have proved the existence of N.

How do we prove that L, the limit of g(n) as N approaches infinity, is infinity? We use L'Hopital's rule.

L'Hopital's rule says that we can find the limit of the ratio of two functions by taking the ratio of their derivatives: https://en.wikipedia.org/wiki/L%27H%C3%B4pital%27s_rule

Well, g(n) is a ratio of functions (b*2^n) and (a*n^2). So, the limit we are looking for is also equal to the limit of: (b*log(2)*2^n)/(a*2*n)

We're still not done, because there's still an n in the denominator. We can apply L'Hopital's rule again to get: (b*(log(2))^2*2^n)/(a*2)

This is clearly an unbounded function. It's just a constant times 2^n. (You can easily prove 2^n is unbounded.) It followed from L'Hopital's rule that the limit of g(n) as n approaches infinity is the same as the limit of this function.

Thus, we have proved that the limit of g(n) = (b*2^n)/(a*n^2) as n approaches infinity is infinity. From the definition of limit, if M = 1, then there is an N such that for all n > N, g(n) > M = 1. We have thus found N such that for all n > N, a*n^2 < b*2^n, as we had set out to do originally. This is the definition of O(n^2) < O(2^n). QED!!!

Touchback