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.
Asked
Active
Viewed 37 times
1
-
2What is the definition of little o you use? – Eugene Jan 31 '17 at 04:21
-
And what is $k$? – David Richerby Jan 31 '17 at 10:21
-
That limit is only 0 if n = 0. For any n > 0, it is 4/n > 0. – gnasher729 Jan 31 '17 at 11:08
-
In other words, there is a typo - $x$ should be $n$ in the limit. – Yuval Filmus Jan 31 '17 at 13:03
1 Answers
2
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$.
Rick Decker
- 8,718