Finding big O of a function

666 Views Asked by At

How do I find Big O of function which are polynomial fractions

$$f(x) = \frac {x^4 + x^2 + 1}{x^3 + 1}$$

The same question is posted here (Finding Big-O with Fractions) but i dont understand the explanation on how from the following we concluded that it is order x $$f(x) = \frac {x^4 + x^2 + 1}{x^3 + 1} = \frac{(x^4 + x^2 +1)/x^3}{(x^3 + 1)/x^3} = \frac{x + \frac{1}{x} + \frac{1}{x^3}}{1 + \frac{1}{x^3}}$$ and you can prove directly from this that $f(x) = O(x)$. Also, what are the witness variables for the above proof?

2

There are 2 best solutions below

0
On BEST ANSWER

Start from the definition of Big O - $f$ is in $\Theta(x)$ if we can find $c_l$ and $c_u$ such that $c_l x < f(x) < c_u x$ for all $x$ greater than some $x_0$. Try showing this with $c_l = \frac{1}{2} $ and $c_2 = 2$.

EDIT: Sorry, I gave the definition of $f$ is in $\Theta(x)$. $f$ is in $O(x)$ if we can find $c$ such that $f(x) < c x$ for all $x$ greater than some $x_0$.But note that if $f$ is $\Theta(x)$, then it is also $O(x)$ and this function in question is indeed $\Theta(x)$.

0
On

For every $x\geqslant1$, $x\leqslant f(x)\leqslant x+1$. Can you conclude?