Prove or disprove the following statement using the definition of big-Θ: NOTE: I am not provign big O here I am proving big-Θ
Prove or disprove the following statement using the definition of big-Θ:
$$n^2−4n = Θ(2^n)$$
so, by definition, $$T(N)=O(h(N))$$ and $$T(N)=Ω(h(N))$$ must both hold.
checking condition 1, $$2^n*c≥n^2≥n^2-4n$$
and so we choose $$c=5, n=1$$
because $$2^n≥n^2$$ for all$$N≥n=1$$
and we conclude $$T(N)=O(h(N))$$
Now, checking condition 2,
$$c*2^n≤n^2-4n≤n^2 $$
but because we showed that $$2^n≥n^2$$ our check on condition two implies that $$2^n=n^2$$
but if we pick $$c=5$$ we get $$32=25$$ which is untrue and in conclusion we have disproved $$n^2−4n = Θ(2^n)$$

This is correct, for $Ω$ as well.
