How do I prove that a constant $C$ exists that matches these bounds?

47 Views Asked by At

For $n \in \mathbb{Z}^+$, given any function $T(n)$ such that $T(n) = \Omega(n^3)$ and $T(n) = O(n^4)$, how can I prove that constants $C$ and $N$ exist such that

$$ n^3 + 10 \le CT(n) \le n^4 $$

for all $n > N$?

My initial attempts have stemmed from the definitions of big-O. We can definitely prove that there exists constants such that:

$$ C_1(n^3 + 10) \le T(n) \le C_2n^4 $$

for all $n > N'$, but I can't compute a single constant $C$ that would work for the first inequality.

1

There are 1 best solutions below

0
On

The assertion is wrong. Try $T(2n)=n^3$ and $T(2n+1)=3n^4$.