Why does $f_{1}(n) = 10n^3 + 5n^2 + 17 \in \theta(n^3)$?

Question

I saw this in this lecture : Asymptotic Notation at the 15 minute mark. But I don't understand it. And also why does $f_{2}(n) = 2n^3 + 3n + 79 \in\theta(n^3)$? I don't understand the proof.

Answer 1

Until you specify what exactly you don't understand from the video's explanation, I will recap the definitions here.

We say that a function $f(n)$ is assymptotically bounded both above and below by a function $g(n)$ if and only if there exist positive real numbers $k_1,k_2$ and $N$ such that for all $n\geq N$ we have $$k_1\cdot g(n)\leq f(n)\leq k_2\cdot g(n)$$

If so, then we write it with symbols as $f(n)=\Theta(g(n))$

Informally, we can think of it as though the functions $f$ and $g$ both "grow at the same speed" relatively speaking. A function like $n^2$ grows much faster than a function like $n$, but they are both dwarfed by a function like $n^3$. On the other hand, a function like $2^n$ grows much faster than the others so far, but that is childs play compared to $3^n$ which is itself nothing compared to $3^{(3^n)}$ which is itself nothing compared to $\underbrace{n^{n^{.^{.^{.^{n}}}}}}_{n~\text{times}}$. Even bigger and bigger functions can be made. So, when two "act pretty much the same" we like to know it and label it as such.

---

In the examples, we wish to show that $\color{purple}{10n^3+5n^2+17} = \Theta(\color{green}{n^3})$. That is to say, we want to know if there is some point at which $\color{green}{n^3}$ times some positive constant $\color{red}{k_1}$ will always be smaller than $\color{purple}{10n^3+5n^2+17}$, and we also want to know if there is some point at which $\color{green}{n^3}$ times some positive constant $\color{blue}{k_2}$ will always be bigger than $\color{purple}{10n^3+5n^2+17}$.

We see that for all positive $n$ (i.e. for all $n\geq 1$) one has:

$$\color{red}{1}\cdot \color{green}{n^3}\leq 10n^3\leq \color{purple}{10n^3+5n^2+17}\leq 10n^3+5n^3+17n^3\leq \color{blue}{32}\cdot\color{green}{n^3}$$

Indeed, the inequality holds (it doesn't even require induction to prove). Letting $k_1=1, k_2=32,$ and $N=1$, this shows that $10n^3+5n^2+17$ satisfies the definition given above for $10n^3+5n^2+17=\Theta(n^3)$.

---

Very informally, this should be immediately apparent as the "biggest part" of $10n^3+5n^2+17$ is a constant multiple of $n^3$. In general, if you have several things being added, you can ignore all of them except the "fastest growing piece" and compare that way. For example, I know without having to check formally that $34n^7+10n^2-5+\frac{1}{n}$ is in fact asymptotically bounded above and below by $n^7$. Similarly I know that $34n^7+10n^2-5+\frac{1}{n}$ is not asymptotically bounded above and below by $n^2$ (since the $34n^7$ piece grows much faster than $n^2$ ever could).