# Big O and Growth of Functions

Printable View

• 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 $\displaystyle n$ such that $\displaystyle f(x)$ is $\displaystyle O(x^n)$ for each of these functions.

a) $\displaystyle f(x) = 2x^2+x^3logx$
b) $\displaystyle f(x) = 3x^5+(logx)^4$
c) $\displaystyle f(x) = (x^4+x^2+1)/(x^4+1)$
d) $\displaystyle 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 $\displaystyle n$ such that $\displaystyle f(x)$ is $\displaystyle O(x^n)$ for each of these functions.

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

First do you have a definition of what:

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

means?

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

$\displaystyle |f(x)|<k |x^n|$

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

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

$\displaystyle |2x^2+x^3\log(x)|<k|x^3|$

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

$\displaystyle |2x^2+x^3\log(x)|<k|x^4|$

So the least integer $\displaystyle n$ such that:

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

is $\displaystyle 4$

CB