How I can prove that: $$ ((n^2) − 3*n + 2) ∈ θ(n^2) $$ using the definition of $θ$ ?
θ : an asymptotic notation in data structure algorithm.
Asked
Active
Viewed 175 times
-1
-
1Welcome to MSE! I'm unsure what you mean by "using the definition of $\theta$." Is $\theta(x^2)$ a function on $x$? – Eric Snyder Feb 23 '21 at 22:42
-
2Uh, that depends on what the definition of $\theta$ is. What the heck IS the definition of $\theta$? – fleablood Feb 23 '21 at 22:44
-
- Big Theta Proof on polynomial function, 1. Big-O Notation - Prove that $n^2 + 2n + 3$ is $\mathcal O(n^2)$, 2. How to prove Big Theta on polynomial function?, 3. How to prove any polynomial of degree k is in Θ(nk)?, ...
– Vepir Feb 23 '21 at 22:47 -
θ : an asymptotic notations in data structure algorithm. – Sara Feb 23 '21 at 23:57
-
@ola : Others are right that you should have provided your working definition of $\Theta$ (that's \Theta not \theta) in the body of your Question. There are variations in the definitions of asymptotic notation (contrast Knuth's $\Omega$ with the number theoretic version). – Eric Towers Feb 24 '21 at 14:12
1 Answers
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.
Eric Towers
- 67,037