• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon

Suggested languages for you:

Americas

Europe

Q50E

Expert-verified
Found in: Page 217

### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095

# Show that if ${f}{\left(}{x}{\right)}{=}{{a}}_{{n}}{{x}}^{{n}}{+}{{a}}_{n-1}{{x}}^{n-1}{+}{\dots }{+}{{a}}_{{1}}{x}{+}{{a}}_{{0}}{,}$, where ${{a}}_{{0}}{,}{{a}}_{{1}}{,}{.}{.}{.}{.}{.}{,}{{a}}_{n-1}{,}$ and ${a}_{n}$ are real numbers and an ${{a}}_{{n}}{\ne }{0}$, then data-custom-editor="chemistry" ${\mathrm{f}}{\left(}{\mathrm{x}}{\right)}$ is ${\Theta }{\left(}{{x}}^{{n}}{\right)}$. Big-O, big-Theta, and big-Omega notation can be extended to functions in more than one variable. For example, the statement ${f}\left(x,y\right)$ is ${O}{\left(}{g}{\left(}{x}{,}{y}{\right)}{\right)}$ means that there exist constants C, ${{k}}_{{1}}$ , and ${{k}}_{{2}}$ such that ${|}{f}{\left(}{x}{,}{y}{\right)}{|}{\le }{C}{|}{g}{\left(}{x}{,}{y}{\right)}{|}$ whenever ${x}{>}{{k}}_{{1}}$ and ${x}{>}{{k}}_{{2}}$.

It is given that $f\left(x\right)={a}_{n}{x}^{n}+{a}_{n-1}{x}^{n-1}+\dots +{a}_{1}x+{a}_{0}$, where ${a}_{0},{a}_{1},.....,{a}_{n-1},$ and ${a}_{n}$ are real numbers then we have to prove that $f\left(x\right)$ is $\Theta \left({x}^{n}\right)$.

See the step by step solution

## Step 1:

$\begin{array}{r}f\left(x\right)={a}_{n}{x}^{n}+{a}_{n-1}{x}^{{x}^{n-1}+\dots +{a}_{1}x+{a}_{0}}\\ |f\left(x\right)|=\left|{a}_{n}{x}^{n}+{a}_{n-1}{1}^{{x}^{n-1}+\dots +{a}_{1}x+{a}_{0}}\right|\end{array}$

Assume b=max(1,${a}_{0},{a}_{1},.....,{a}_{n-1}$)

Thus x> max(1,${a}_{0},{a}_{1},.....,{a}_{n-1}$)

$\begin{array}{r}⇒|f\left(x\right)|\le \left|{a}_{n}{x}^{n}+x{x}^{n-1}+\dots +xx+x\right|\\ ⇒|f\left(x\right)|\le \left|{a}_{n}{x}^{n}+{x}^{n}+\dots +{x}^{2}+x\right|\\ ⇒|f\left(x\right)|\le \left|{a}_{n}{x}^{n}+{x}^{n}+\dots +{x}^{n}+{x}^{n}\right|\\ ⇒|f\left(x\right)|\le \left|{a}_{n}{x}^{n}+n{x}^{n}\right|\\ ⇒|f\left(x\right)|\le \left|{a}_{n}+n\right|{x}^{n}\parallel \end{array}$

Hence, it can be said that f(x) is $O\left({x}^{n}\right)$ with constants b=max(1,${a}_{0},{a}_{1},.....,{a}_{n-1}$) and C= $|{a}_{n}+n|$

## Step 2:

$\begin{array}{r}f\left(x\right)={a}_{n}{x}^{n}+{a}_{n-1}{x}^{n-1}+\dots +{a}_{1}x+{a}_{0}\\ |f\left(x\right)|=\left|{a}_{n}{x}^{{x}^{n}+{a}_{n-1}{1}^{{x}^{n-1}}+\dots +{a}_{1}x+{a}_{0}}\right|\end{array}$

Assume b=min (1,${a}_{0},{a}_{1},.....,{a}_{n-1}$)

Thus x> min (1,${a}_{0},{a}_{1},.....,{a}_{n-1}$)

$\begin{array}{r}⇒|f\left(x\right)|\ge \left|b{x}^{n}+b{x}^{n-1}+\dots +bx+b\right|\\ ⇒|f\left(x\right)|\ge \left|b\left({x}^{n}+{x}^{n-1}+\dots +{x}^{1}+x\right)\right|\\ ⇒|f\left(x\right)|\ge |b|\left|{x}^{n}+{x}^{n-1}+\dots +{x}^{1}+x\right|\end{array}$

Hence, it can be said that f(x) is $\Omega \left({x}^{n}\right)$ with constants b=min (1,${a}_{0},{a}_{1},.....,{a}_{n-1}$) and C=$\left|b\right|$

## Step 3:

As we know that $f\left(x\right)$ is $O\left({x}^{n}\right)$ and $f\left(x\right)$ is $\Omega \left({x}^{n}\right)$.

Hence, by applying the definition of Big-Theta Notation, f (x) is $\Theta \left({x}^{n}\right)$.