Little O Computation: $4n\:\in \:o\left(n^2\right)$

Question

For this, I know you can use calculus techniques and set $\lim _{x\to \infty }\left(\frac{4n}{n^2}\right)$ and get 0. Though, I'm wanting to know how you can get a specific constant and k values.

Answer 1

Since you don't want to use the limit, we can in this case use the definition (see here for details): $$ f(n)=o(g(n)) \stackrel{\text{def}}\equiv \forall k>0\,\exists N\ge 0\, \forall n\ge N\,[\:f(n)\le k\cdot g(n)\:] $$ In other words, the definition is exactly the same as for big-O, except that the inequality eventually holds for all positive constant multiples $k$.

With this in mind, choose any positive $k$. Then to have $$ 4n\le k\:n^2 $$ we need the equivalent $$ \frac{4}{k}\le n $$ so for any positive $k$ we'll have $4n\le n^2$ for all $n\ge N = 4/k$.