Question

Suppose that$\mathit{f}\mathbf{\left(}\mathit{x}\mathbf{\right)}\mathbf{,}\mathit{g}\mathbf{\left(}\mathit{x}\mathbf{\right)}\mathbf{\text{and}}\mathit{h}\mathbf{\left(}\mathit{x}\mathbf{\right)}$ are functions such that $\mathit{f}\mathbf{\left(}\mathit{x}\mathbf{\right)}\mathbf{\text{is}}\mathbf{\Theta }\mathbf{\left(}\mathit{g}\mathbf{\right(}\mathit{x}\mathbf{\left)}\mathbf{\right)}$and $\mathit{g}\mathbf{\left(}\mathit{x}\mathbf{\right)}\mathbf{\text{is}}\mathbf{\Theta }\mathbf{\left(}\mathit{h}\mathbf{\right(}\mathit{x}\mathbf{\left)}\mathbf{\right)}$. Show that $\mathit{f}\mathbf{\left(}\mathit{x}\mathbf{\right)}\mathbf{\text{is}}\mathbf{\Theta }\mathbf{\left(}\mathit{h}\mathbf{\right(}\mathit{x}\mathbf{\left)}\mathbf{\right)}$.

Short answer

In the question, it is given $f\left(x\right),g\left(x\right)\text{and}h\left(x\right)$and are the functions such that $f\left(x\right)\text{is}\mathrm{\Theta }\left(g\right(x\left)\right)$and $g\left(x\right)\text{is}\mathrm{\Theta }\left(h\right(x\left)\right)$ . We have to prove that$f\left(x\right)\text{is}\mathrm{\Theta }\left(h\right(x\left)\right)$ .

Step-by-step solution

Step 1:

For $f\left(x\right)\text{is}\mathrm{\Theta }\left(g\right(x\left)\right)$ , applying the definition of Big-theta Notation

$\begin{array}{r}\left|f\right(x\left)\right|\le a_1\left|g\right(x\left)\right|\text{if}\mathrm{x}>b_1\\ \left|f\right(x\left)\right|\ge a_2\left|g\right(x\left)\right|\text{if}\mathrm{x}>b_2\end{array}$

Where $a_1,a_2,b_1\text{and}{b}_2$are constants.

For $g\left(x\right)\text{is}\mathrm{\Theta }\left(h\right(x\left)\right)$, applying the definition of Big-theta Notation

$\begin{array}{l}\left|g\right(x\left)\right|\le a_3\left|h\right(x\left)\right|\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}\mathrm{x}>b_3\\ \left|g\right(x\left)\right|\ge a_4\left|h\right(x\left)\right|\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\hspace{0.25em}\text{if}\mathrm{x}>b_4\end{array}$

Where $a_3,a_4,b_3\text{and}{b}_4$are constants.

Step 2:

We can take,$\mathrm{b}=max\left(b_1,b_2,b_3,b_4\right)$

We know that, $\left|f\right(x\left)\right|\le a_1\left|g\right(x\left)\right|\text{and}\left|g\right(x\left)\right|\le a_3\left|h\right(x\left)\right|\mid$

So, $f\left(x\right)\text{is}O\left(h\right(x\left)\right)\text{with}\mathrm{b}=max\left(b_1,b_2,b_3,b_4\right)\text{and}\mathrm{a}=a_1{a}_3$

Also, $\left|f\right(x\left)\right|\ge a_2\left|g\right(x\left)\right|\text{and}\left|g\right(x\left)\right|\ge a_4\left|h\right(x\left)\right|$

So, $f\left(x\right)\text{is}\mathrm{\Omega }\left(h\right(x\left)\right)\text{with}\mathrm{b}=max\left(b_1,b_2,b_3,b_4\right)\text{and}\mathrm{a}=a_2{a}_4$

Step 3:

By using $f\left(x\right)\text{is}O\left(h\right(x\left)\right),f\left(x\right)\text{is}\mathrm{\Omega }\left(h\right(x\left)\right)$

Hence, by using the definition of Big-theta Notation, we can conclude that$f\left(x\right)\text{is}\mathrm{\Theta }\left(h\right(x\left)\right)$