According to this link:
We need the notation for the lower bound. A capital omega $\Omega$ notation is used in this case.
We say that $f(n) = \Omega(g(n))$ when there exist constant $c$ that $f(n) \geq c \cdot g(n)$ for for all sufficiently large $n$. Examples:
- $n = \Omega(1)$
- $n^2 = \Omega(n)$
- $n^2 = \Omega(n \cdot \log n)$
- $2n + 1 = O(n)$
I need to verify whether $T(n^2) = Ω(n)$. Because I can't seem to think that a quadratic run-time can have a linear lower bound run-time.
I am confused so I might be wrong though.