Big Theta

Ex) Prove that $T(N) = N^3 + 3N^2 + 10N$ is $\Theta(N^3)$

Need to prove that both $T(N)$ is $\Omega(N^3)$ and $T(N)$ is $O(N^3)$

Step 1: Big-O

First, let's do big-O (showing that N^3 is an upper bound, up to some constant)

$T(N) = N^3 + 3N^2 + 10N \leq N^3 + 3N^3 + 10N^3, N > 1$

$T(N) \leq 14 N^3, N > 1$

We just found a constant $c = 14$ so that

$T(N) \leq cN^3, N > 1$

Step 1: Big-$\Omega$

We need to show that $N^3$ is a lower bound, we need to find a constant $c$ so that

$T(N) \geq cN^3$

$T(N) = N^3 + 3N^2 + 10N \geq N^3, N > 1$

$T(N) \geq N^3$

Therefore, $T(N)$ is $\Theta(N)$

$N^3$ is $O(N^8)$

$N^3 + 3N^2 + 10N$ is $\Theta(N^3)$, $N^3$ is the lowest upper bound that I can find, and $N^3$ is also the greatest lower bound I can find

The bound is "tight"; can't do any better or worse