Prove that running time $T(n) = n^3 + 20n \space \space \text{is}\space \space Ω(n^2)$
My attempt:
This question is given on this PDF(que-4).
I have understood the big-oh notation and it's conditions. I understood the given examples of bog-oh on given Pdf.
My question is:
Why numerator has $n$ in $n + \cfrac{20}{n}\geq c$, and how they calculated: The left side of this inequality has the minimum value of $8.94$ for $n = \sqrt{20} ≅ 4.47$
This answer is trying to explain the linked solution. This is not the most efficient way to prove the desired relationship (see the comments for more efficient ways to prove this).
Starting with the desired inequality $$ n^3+20n\geq cn^2, $$ they divide both sides by $n^2$ to get $$ \frac{n^3}{n^2}+\frac{20n}{n^2}\geq c. $$ Simplifying, the result is $$ n+\frac{20}{n}\geq c. $$ Next, they use calculus to minimize the function $$ f(x)=x+\frac{20}{x}. $$ Since $$ f'(x)=1-\frac{20}{x^2}, $$ $f$ has a local extrema at $x=\sqrt{20}$. This can be seen to be a minimum by considering the signs of $f'$. Therefore, the smallest that $f(x)$ can be is $2\sqrt{20}$. Therefore, for all $n$, $$ n+\frac{20}{n}\geq 2\sqrt{20}. $$ Therefore, $2\sqrt{20}$ is a good choice for $c$ to make $$ n^3+20n\geq 2\sqrt{20}n^2 $$ always true.
Note that the inequality $n+\frac{20}{n}\geq c$ can be dealt with in a much simpler way by observing that $n+\frac{20}{n}\geq n$ and since we're dealing with $n\geq 1$, $n+\frac{20}{n}\geq n\geq 1$. The solution of interest gives a larger $c$ (so a "tighter bound"), but all that matters is that there is a $c$.