Big O Notation question

[bori]

I have a problem:

2^(n+1) +n! +34

From what I understand, I'm supposed to find the function that dominates the rest, meaning it grows the fastest. Just by looking at the equation, I have to say n! grows the fastest, but I want to know the formal way of solving such a problem. How would one go about finding the answer formally?

Thanks, Bori

[willriker]

Factorial or exponential function
0! = 1
1! = 1
2! = 1*2 = 2
3! = 1*2*3 = 6
4! = 1*2*3*4 = 24
5! = 1*2*3*4*5 = 120
6! = 1*2*3*4*5*6 = 720
7! = 1*2*3*4*5*6*7 = 5040

or

2^(n+1)

n(0) = 2
n(1) = 2*2 = 4
n(2) = 2*2*2 = 8
n(3) = 2*2*2*2 = 16
n(4) = 2*2*2*2*2 = 32
n(5) = 2*2*2*2*2*2 = 64
n(6) = 2*2*2*2*2*2*2 = 128
n(7) = 2*2*2*2*2*2*2*2 = 256

[Kaylia]

I have a problem:

2^(n+1) +n! +34

From what I understand, I'm supposed to find the function that dominates the rest, meaning it grows the fastest. Just by looking at the equation, I have to say n! grows the fastest, but I want to know the formal way of solving such a problem. How would one go about finding the answer formally?

Thanks, Bori

n!!

[edit]
wait, no, thats slower


n!^2

[bori]

n!!

[edit]
wait, no, thats slower


n!^2

How did you go about getting that?

[Kaylia]

I have a problem:

2^(n+1) +n! +34

From what I understand, I'm supposed to find the function that dominates the rest, meaning it grows the fastest. Just by looking at the equation, I have to say n! grows the fastest, but I want to know the formal way of solving such a problem. How would one go about finding the answer formally?

Thanks, Bori

First of all, you will never have to make an algorithm that is less efficient. Finding something bigger isn't an issue.


Secondly, you're right when you target the n!, since it's the term that grow the fast. Finding something that grow faster than an expectional isn't hard. You just need to add something to make it grow even faster (an)! (n!)! (n!)^2 all works


If dominate mean "is higher at any point", you will to take into account the +34 and 2^(n+1), but it's not hard.


Looking for formal way? I cant really think of any formal way to do it. If it was in my homeworks, I would simply start and say "n!" is the dominant term, and simply mention it was replaced with a bigger term.

[willriker]

Factorial or exponential function
0! = 1
1! = 1
2! = 1*2 = 2
3! = 1*2*3 = 6
4! = 1*2*3*4 = 24
5! = 1*2*3*4*5 = 120
6! = 1*2*3*4*5*6 = 720
7! = 1*2*3*4*5*6*7 = 5040

or

2^(n+1)

n(0) = 2
n(1) = 2*2 = 4
n(2) = 2*2*2 = 8
n(3) = 2*2*2*2 = 16
n(4) = 2*2*2*2*2 = 32
n(5) = 2*2*2*2*2*2 = 64
n(6) = 2*2*2*2*2*2*2 = 128
n(7) = 2*2*2*2*2*2*2*2 = 256

If you really want to get fancy with it, the 34 will dominate the equation until n = 5. then the n! will dominate the equation. At no point will 2^(n+1) dominate the equation.

You could also just plug this term of the equation into just about any graphing calculator.

[Kaylia]

How did you go about getting that?

n!! = n * (n-2) * (n -4 )*... is smaller than n! = n * (n-1) * (n-2)...

It's a stupid notation, but I meant to say something like this (n!)!.

Because every n are integer, (n!) >= n, meaning (n!)!> n.

[Selamis]

False advertising title. Came in thread to expect discussion about orgasms, and big O faces.

[Xno Kappa]

Came in this thread expecting a discussion on the anime.

[Pyree]

Normally this sort of question is just mental math, you just know which functions grow bigger as they approach infinity. But if you have to prove it, all you'd have to do would be to graph each portion separately and be sure to show all the intersections. In order to do this, break the equation up into the smallest parts you can.

When working with Big O notation, you get rid of all the constants because they ultimately don't impact the function very much as you go to infinity. For the function 2^(n+1) +n! +34, you only need to graph f(n) = 2^n; g(n) = n!; h(n) = 1. If f(n) grows the largest, the answer is O(c^n); if g(n) grows the largest, the answer is O(n!); if h(n) grows the largest, the answer is O(1). You can see why I say this is mental math, because after you break it down into such simple functions the answer is obvious...

[willriker]

O(n!)

[Erza]

O(exp(n))

[Yuri-G]

Came in this thread expecting a discussion on the anime.

came in this thread expecting a discussion on orgasms myself.

[Colenzo]

http://i45.tinypic.com/dzgh7d.jpg
wtf do you guys want

[DionyShiva]

Obviously, the 34 is not going to be the fastest growing term, so look at 2^(n+1) and n!:

n! = n(n-1)(n-2)(n-3)...

If you were to expand the right side, the first term of each factor would multiply together to form an n^n, and the other terms would be on the order of n^(n-1), n^(n-2), etc...

n! = n^n + O(n^(n-1))

n^n + O(n^(n-1)) is necessarily larger than 2^(n+1) for all n > 3 just by looking at the first term of the left side alone

Therefore, the factorial term is the fastest growing term.

[joft]

another justification:

e^x = sum n=0 to infinity x^n/n!

this series converges for all x, and specifically for x = 2

convergence of series implies the terms go to zero

hence 2^n/n! -> 0 as n -> infinity

it's not a proof from first principles since it uses facts (like the series definition of exponential) that are more sophisticated than this problem itself. but it was the first thing that came to my mind

[Olo401]

http://i45.tinypic.com/dzgh7d.jpg
wtf do you guys want

oh good lord lol..

[Zhais]

I came in expecting a programming question