Chapter 3: Q46E (page 217)

Show that if $f_{1} (x)$ and $f_{2} (x)$ are functions from the set of positive integers to the set of real numbers androle="math" localid="1668678872142" $f_{1} (x) is Θ (g_{1} (x)) and f_{2} (x) is Θ (g_{2} (x)), then (f_{1} f_{2}) (x) is$ role="math" localid="1668678882006" $Θ (g_{1} (x))$ .

Short Answer

Expert verified

In the question, it is given that $f_{1} (x)$ and $f_{2} (x)$ are the functions such that $f_{1} (x) and f_{2} (x)$ both are $Θ (g (x))$ . And we have to prove that $(f_{1} f_{2}) (x) is Θ (g_{1} g_{2} (x))$ .

Step by step solution

Step 1:

For $f_{1} (x) is Θ (g_{1} (x))$ , applying the definition of Big-theta Notation

$\begin{aligned} |f_{1} (x)| \leq a_{1} |g_{1} (x)| if x > b_{1} \\ |f_{1} (x)| \geq a_{2} |g_{1} (x)| if x > b_{2} \end{aligned}$

Where, $a_{1}, a_{2}, b_{1} and b_{2}$ are constants.

For $f_{2} (x) is Θ (g_{2} (x))$ is , applying the definition of Big-theta Notation

$\begin{aligned} |f_{2} (x)| \leq a_{3} |g_{2} (x)| if x > b_{3} \\ |f_{2} (x)| \geq a_{4} |g_{2} (x)| if x > b_{4} \end{aligned}$

Where $a_{3}, a_{4}, b_{3} and b_{4}$ are constants

Step 2:

We can take, b = max $(b_{1}, b_{2}, b_{3}, b_{4})$

Multiplying $|f_{1} (x)| \leq a_{1} |g_{1} (x)| and |f_{2} (x)| \leq a_{3} |g_{2} (x)|$

$\Rightarrow |f_{1} (x)| |f_{2} (x)| \leq a_{1} |g_{1} (x)| a_{3} |g_{2} (x)|$

We get, $|f_{1} f_{2} (x)| \leq a_{1} a_{3} |g_{1} g_{2} (x)|$

Hence, $(f_{1} f_{2}) (x) is O (g_{1} g_{2} (x)) with b = max (b_{1}, b_{2}, b_{3}, b_{4}) and a = a_{1} a_{3}$

Multiplying $|f_{1} (x)| \geq a_{2} |g_{1} (x)| and |f_{2} (x)| \geq a_{4} |g_{2} (x)|$

$\Rightarrow |f_{1} (x)| |f_{2} (x)| \geq a_{2} |g_{1} (x)| a_{4} |g_{2} (x)|$

We get, $|f_{1} f_{2} (x)| \geq a_{2} a_{4} |g_{1} g_{2} (x)|$

So, $(f_{1} f_{2}) (x) is Ω (g_{1} g_{2} (x)) with b = max (b_{1}, b_{2}, b_{3}, b_{4}) and a = a_{2} a_{4}$

Step 3:

By using $(f_{1} f_{2}) (x) is O {(g_{1} g_{2} (x))}^{*} (f_{1} f_{2}) (x) is Ω (g_{1} g_{2} (x))$

Hence, by using the definition of Big-theta Notation, we can conclude that is $(f_{1} f_{2}) (x) i s Θ (g_{1} g_{2} (x))$ .

Recommended explanations on Math Textbooks

View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Show that if $f_{1} (x)$ and $f_{2} (x)$ are functions from the set of positive integers to the set of real numbers androle="math" localid="1668678872142" $f_{1} (x) is Θ (g_{1} (x)) and f_{2} (x) is Θ (g_{2} (x)), then (f_{1} f_{2}) (x) is$ role="math" localid="1668678882006" $Θ (g_{1} (x))$ .

Short Answer

Step by step solution

Step 1:

Step 2:

Step 3:

One App. One Place for Learning.

Most popular questions from this chapter

Recommended explanations on Math Textbooks

Mechanics Maths

Calculus

Discrete Mathematics

Statistics

Decision Maths

Logic and Functions

Study anywhere. Anytime. Across all devices.

Company

Product

Help

Show that if f1xand f2(x)are functions from the set of positive integers to the set of real numbers androle="math" localid="1668678872142" f1(x)isΘ(g1(x))andf2(x)isΘ(g2(x)), then(f1f2)(x)isrole="math" localid="1668678882006" Θ(g1(x)) .

Short Answer

Step by step solution

Step 1:

Step 2:

Step 3:

One App. One Place for Learning.

Most popular questions from this chapter

Recommended explanations on Math Textbooks

Mechanics Maths

Calculus

Discrete Mathematics

Statistics

Decision Maths

Logic and Functions

Study anywhere. Anytime. Across all devices.

Show that if $f_{1} (x)$ and $f_{2} (x)$ are functions from the set of positive integers to the set of real numbers androle="math" localid="1668678872142" $f_{1} (x) is Θ (g_{1} (x)) and f_{2} (x) is Θ (g_{2} (x)), then (f_{1} f_{2}) (x) is$ role="math" localid="1668678882006" $Θ (g_{1} (x))$ .