Question

If ${\mathit{f}}_{\mathbf{1}}\mathbf{\left(}\mathit{x}\mathbf{\right)}\mathbf{\text{and}}{\mathit{f}}_{\mathbf{2}}\mathbf{\left(}\mathit{x}\mathbf{\right)}$are functions from the set of positive integers to the set of positive real numbers and ${\mathit{f}}_{\mathbf{1}}\mathbf{\left(}\mathit{x}\mathbf{\right)}\mathbf{\text{and}}{\mathit{f}}_{\mathbf{2}}\mathbf{\left(}\mathit{x}\mathbf{\right)}$are both $\mathbf{\Theta }\mathbf{\left(}\mathit{g}\mathbf{\right(}\mathit{x}\mathbf{\left)}\mathbf{\right)}$, $\mathbf{\text{is}}\left(f_1-f_2\right)\mathbf{\left(}\mathit{x}\mathbf{\right)}\mathbf{\text{also}}\mathbf{\Theta }\mathbf{\left(}\mathit{g}\mathbf{\right(}\mathit{x}\mathbf{\left)}\mathbf{\right)}$? Either prove that it is or give a counterexample.

Short answer

In the question, it is given that $f_1\left(x\right)\text{and}{f}_2\left(x\right)$ are the functions such that $f_1\left(x\right)\text{and}{f}_2\left(x\right)$ both are$\mathrm{\Theta }\left(g\right(x\left)\right)$ .

Step-by-step solution

Step 1:

Assume ,$f_1\left(x\right)=x+1,f_2\left(x\right)=x\text{and}g\left(x\right)=x$

Here, both $f_1\left(x\right)=x+1\text{and}{f}_2\left(x\right)=x\text{are}\mathrm{\Theta }\left(g\right(x\left)\right)\text{. So,}{f}_1\left(x\right)\text{and}{f}_2\left(x\right)$ are both $\mathrm{\Theta }\left(g\right(x\left)\right)$has become true.

Step 2:

$f_1\left(x\right)=x+1,f_2\left(x\right)=x$

So,

role="math" localid="1668679712933" $$\begin{gathered} so\left(f_1-f_2\right)\left(x\right) \\ =f_1\left(x\right)-f_2\left(x\right) \\ =x+1-x \\ =1 \end{gathered}$$

Hence, By applying the definition of Big-theta Notation, we can say that $\left(f_1-f_2\right)\left(x\right)\text{is}\mathrm{\Theta }\left(1\right)$.

So, $\left(f_1-f_2\right)\left(x\right)=1\text{is not}\mathrm{\Theta }\left(g\right(x\left)\right)$

Here, we have proved that $\left(f_1-f_2\right)\left(x\right)\text{is not}\mathrm{\Theta }\left(g\right(x\left)\right)$by using counterexample.