Prove using the definition of θ.

Question

How I can prove that: $$ ((n^2) − 3*n + 2) ∈ θ(n^2) $$ using the definition of $θ$ ?

θ : an asymptotic notation in data structure algorithm.

Answer 1

One way is to find, on $n \in [1,\infty)$, the minimum and maximum of $$ \frac{n^2 -3n + 2}{n^2} \text{.} $$ Let $\ell$ be the global minimum and $u$ be the global maximum. Then you know $$ \ell n^2 \leq n^2 - 3n + 2 \leq u n^2 \text{,} $$ where $\ell$ and $u$ are constants (independent of $n$). This establishes the result you want.

In this particular case, there is a critical point giving the lower bound, $-1/8$, and then you can take a limit to get the upper bound, $1$.

Of course, since $\Theta$ allows the bounds to hold on any interval of the form $[n_0, \infty)$. You can choose to optimize on a smaller half-line. If, say, you optimize on $[5,\infty)$, the rational function above is strictly monotonically increasing, so you can evaluate the ratio at $5$ to get a lower bound and take the limit as $n \rightarrow \infty$ (which is very, very easy for rational functions and is taught prior to calculus when graphing rational functions) to get an upper bound.