- $f(x)=2x^{2}+x^{3}\log x$
- $f(x)=3x^{5}+(log x)^{4}$
- $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.
Expert Answer
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$.