StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q50E

Expert-verifiedFound in: Page 217

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}{\right(}{x}{,}{y}{\left)}{\right)}$ means that there exist constants C, ${{k}}_{{1}}$ , and ${{k}}_{{2}}$ such that ****${\left|}{f}{\right(}{x}{,}{y}{\left)}{\right|}{\le}{C}{\left|}{g}{\right(}{x}{,}{y}{\left)}{\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)$.

$\begin{array}{r}f\left(x\right)={a}_{n}{x}^{n}+{a}_{n-1}{x}^{{x}^{n-1}+\dots +{a}_{1}x+{a}_{0}}\\ \left|f\right(x\left)\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}\Rightarrow \left|f\right(x\left)\right|\le \left|{a}_{n}{x}^{n}+x{x}^{n-1}+\dots +xx+x\right|\\ \Rightarrow \left|f\right(x\left)\right|\le \left|{a}_{n}{x}^{n}+{x}^{n}+\dots +{x}^{2}+x\right|\\ \Rightarrow \left|f\right(x\left)\right|\le \left|{a}_{n}{x}^{n}+{x}^{n}+\dots +{x}^{n}+{x}^{n}\right|\\ \Rightarrow \left|f\right(x\left)\right|\le \left|{a}_{n}{x}^{n}+n{x}^{n}\right|\\ \Rightarrow \left|f\right(x\left)\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|$

$\begin{array}{r}f\left(x\right)={a}_{n}{x}^{n}+{a}_{n-1}{x}^{n-1}+\dots +{a}_{1}x+{a}_{0}\\ \left|f\right(x\left)\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}\Rightarrow \left|f\right(x\left)\right|\ge \left|b{x}^{n}+b{x}^{n-1}+\dots +bx+b\right|\\ \Rightarrow \left|f\right(x\left)\right|\ge \left|b\left({x}^{n}+{x}^{n-1}+\dots +{x}^{1}+x\right)\right|\\ \Rightarrow \left|f\right(x\left)\right|\ge \left|b\right|\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|$

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)$.

94% of StudySmarter users get better grades.

Sign up for free