# Thread: Proving that a function is equal to a big O function

1. ## Proving that a function is equal to a big O function

Can someone give me a hint to get me started? Below is the problem. It's proving that a function is equal to a big O function.

2. ## Re: Proving that a function is equal to a big O function

$f \sim \mathcal{O}(g) \Leftrightarrow \exists M >0,x_0 \ni x>x_0 \Rightarrow |f| \leq M|g|$

here

$f(n) = 4n^4 + 5n^2 +32$

$g(n) = n^4$

we need to find $M>0,~n_0$

such that

$n>n_0 \Rightarrow | 4n^4 + 5n^2 +32| \leq M |n^4|$

everything is positive so we can drop the absolute value signs

$n>n_0 \Rightarrow (4-M)n^4 + 5n^2 + 32 \leq 0$

$n_0=1,~M=41$ satisfies this inequality, so does

$n_0=3,~M=5$

3. ## Re: Proving that a function is equal to a big O function

So basically if we could find values of n for which f(n) < 0(n^4), then it is true.

4. ## Re: Proving that a function is equal to a big O function

Originally Posted by romsek
$f \sim \mathcal{O}(g) \Leftrightarrow \exists M >0,x_0 \ni x>x_0 \Rightarrow |f| \leq M|g|$

here

$f(n) = 4n^4 + 5n^2 +32$

$g(n) = n^4$

we need to find $M>0,~n_0$

such that

$n>n_0 \Rightarrow | 4n^4 + 5n^2 +32| \leq M |n^4|$

everything is positive so we can drop the absolute value signs

$n>n_0 \Rightarrow (4-M)n^4 + 5n^2 + 32 \leq 0$

$n_0=1,~M=41$ satisfies this inequality, so does

$n_0=3,~M=5$
That is a little too advanced for me. Here is what I got. Check it out.