# Big O and Growth of Functions

• Nov 7th 2008, 07:35 AM
Dharper07
Big O and Growth of Functions
Hey I can't figure this HW assignment out, could anyone help me solve this...it would greatly be appreciated.

Find the least integer $n$ such that $f(x)$ is $O(x^n)$ for each of these functions.

a) $f(x) = 2x^2+x^3logx$
b) $f(x) = 3x^5+(logx)^4$
c) $f(x) = (x^4+x^2+1)/(x^4+1)$
d) $f(x) = (x^3+5logx)/(x^4+1)$
• Nov 8th 2008, 12:15 AM
CaptainBlack
Quote:

Originally Posted by Dharper07
Hey I can't figure this HW assignment out, could anyone help me solve this...it would greatly be appreciated.

Find the least integer $n$ such that $f(x)$ is $O(x^n)$ for each of these functions.

a) $f(x) = 2x^2+x^3logx$
b) $f(x) = 3x^5+(logx)^4$
c) $f(x) = (x^4+x^2+1)/(x^4+1)$
d) $f(x) = (x^3+5logx)/(x^4+1)$

First do you have a definition of what:

$f(x)=O(x^n)$

means?

It means that there exists a positive constant $k$ there exists an $x_0$ such that for all $x>x_0$

$|f(x)|

a) $f(x) = 2x^2+x^3\log(x)$

Here clearly there is no $k$ such that eventualy:

$
|2x^2+x^3\log(x)|$

since $\log(x)$ also grows without bound. But as $\log(x)$ growns more slowly than $x$ (that is $\lim_{x \to \infty} \log(x)/x =0$) we can find $k$ such that:

$
|2x^2+x^3\log(x)|$

So the least integer $n$ such that:

$2x^2+x^3\log(x)=O(x^n)$

is $4$

CB