 # Find the least integer n such that f(x) is O(x^n) for each of these functions. 1. $f(x)=2x^{2}+x^{3}\log x$
2. $f(x)=3x^{5}+(log x)^{4}$
3. $f(x)=\dfrac{x^{4}+x^{2}+1}{x^{4}+1}$

The article aims to find the value of the n for each function given to satisfy the O(x^n) notation. Big-O notation represents the maximum operating time of the algorithm. Therefore, it provides the worst possible algorithm. In computer science, big O notation is used to classify algorithms according to how their working time or space requirements grow as input size. In the theory of numerical analysis, the main notation of O is often used to express the obligation of the distinction between arithmetical function and best-understood guesses; a famous example of such a difference is the word remaining in the prime number theorem.

Part (a)

The function is $f(x)=2x^{2}+x^{3}\log x$

The property $\log x\leq x$ holds when $x >0$.

$f(x)=2x^{2}+x^{3}\log x \leq 2x^{2}+x^{4}$

The maximum power of $x$ in the expression of the $f(x)$ is the smallest $n$ for which $f(x)$ is $O(x^{n})$.

$n=4$

When $x>2$, we have the property $x^{2}>x>2$.

Let’s choose $k=2$ first and then choose $x>2$.

$|f(x)|=|2x^{2}+x^{3}\log x|\leq|2x^{2}+x^{4}|\leq |2x^{2}|+|x^{4}|$

$=2x^{2}+x^{4}\leq x^{4}+x^{4}$

$=2x^{4}$

$=2|x^{4}|$

Thus, $C$ should be at least $2$. Let us then choose $C=2$.

Hence, $f(x)=O(x^{4})$ with $k=2$ and $C=2$.

Part(b)

The function is $f(x)=3x^{5}+(\log x)^{4}$

The maximum power of $x$ in the expression of the $f(x)$ is the smallest $n$ for which $f(x)$ is $O(x^{n})$.

$n=5$

The property $\log x\leq x$ holds when $x, 0$.

When $x>1$, we have the property $x^{4}<x^{5}$.

Let’s choose $k=1$ first and then choose $x>1$.

$|f(x)|=|3x^{5}+(\log x)^{4}|\leq|3x^{5}|+|(\log x)^{4}|$

$=3x^{5}+(\log x)^{4}\leq 3x^{5}+x^{4}$

$=4x^{5}$

$=4|x^{5}|$

Thus, $C$ should be at least $4$. Let us then choose $C=4$.

The Big $O$ notation, $f(x)=O(x^{5})$ with $k=1$ and $C=4$.

Part(c)

The function is $f(x)=\frac{x^{4}+x^{2}+1}{x^{4}+1}$

Let’s determine the quotient of the reminder using long division.

The quotient is $1$ with reminder $x^{2}$.

Rewrite the given fraction

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

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

The maximum power of $x$ in the expression of the $f(x)$ is the smallest $n$ for which $f(x)$ is $O(x^{n})$.

$n=0$

Let’s choose $k=0$ first and then choose $x>0$.

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

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

$=3x^{5}+(\log x)^{4}\leq 3x^{5}+x^{4}<2$

$=2.1$

$=2|x^{o}|$

Thus, $C$ should be at least $2$. Let us then choose $C=2$.

## Numerical Result

-$f(x)=2x^{2}+x^{3}\log x$

The Big $O$ notation, $f(x)=O(x^{4})$ with $k=2$ and $C=2$.

-$f(x)=3x^{5}+(log x)^{4}$

The Big $O$ notation, $f(x)=O(x^{5})$ with $k=1$ and $C=4$.

-$f(x)=\dfrac{x^{4}+x^{2}+1}{x^{4}+1}$

The Big $O$ notation, $f(x)=O(x^{0})=O(1)$ with $k=0$ and $C=2$.

## Example

Determine the least integer $n$ such that $f(x)$ is $O(x^{n}) for the following functions. -$f(x)=2x^{2}+x^{4}\log x$Solution The function is $f(x)=2x^{2}+x^{4}\log x$ The property$\log x\leq x$holds when$x >0$. $f(x)=2x^{2}+x^{4}\log x \leq 2x^{2}+x^{5}$ The highest power of$x$in the expression of the$f(x)$is the smallest$n$for which$f(x)$is$O(x^{n})$. $n=5$ When$x>2$, we have the property$x^{2}>x>2$. Let’s choose$k=2$first and then choose$x>2$. $|f(x)|=|2x^{2}+x^{4}\log x|\leq|2x^{2}+x^{5}|\leq |2x^{2}|+|x^{5}|$ $=2x^{2}+x^{5}\leq x^{5}+x^{5}$ $=2x^{5}$ $=2|x^{5}|$ Thus,$C$should be at least$2$. Let us then choose$C=2\$.