2

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.

David Faux
  • 3,425

1 Answers1

0

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

Did
  • 279,727