Exercise 3.1.5
Prove Theorem 3.1
The theorem states:
For any two functions f(n) and g(n), we have f(n)=Θ(g(n)) if and
only if f(n)=O(g(n)) and f(n)=Ω(g(n)).
From f(n)=Θ(g(n)), we have that:
0≤c1g(n)≤f(n)≤c2g(n)for n>n0
We can pick the constants from here and use them in the definitions of O and
Ω to show that both hold.
From f(n)=Ω(g(n)) and f(n)=O(g(n)):
0≤c3g(n)≤f(n)for all n≥n10≤f(n)≤c4g(n)for all n≥n2
If we let n3=max(n1,n2) and merge the inequalities, we get:
0≤c3g(n)≤f(n)≤c4g(n)for all n>n3
Which is the definiition of Θ.