o notation example
I'm having trouble with this one problem
9n <= cn^3
basically I can get down to
9/c <= n^2
But how do I solve the rest?
definition of little o is
we say f(x)=o(g(x)) .
let f(x)=9*x and g(x)=c*x^3 where c is a positive constant. when x tends to infinity, f(x)/g(x) tends to 0.so we can say f(x)=o(g(x)) .
asyptotic notations are applicable for sufficiently large value of n.so for large value of n
9n << cn^3
for all c>0.
Read this link to undersatnd big-O and little-O link
see in case of your equation, when n=3 it becomes 9*3=23=3^3 so for n<3 9n > n^3. so if you choose c as any number to make 9n<=n^3 for n<3 then it can be in O(n).
You just need to show that for every c there is a n0 such that for all n > n0 : 9n <= n^3 . By just solving this equation to n you get (assuming n positive):
n >= 3/sqrt(c)
Now take n0 = 3/sqrt(c) , which exists and is positive for all c > 0 , then for all n > n_0 with the reverse calculation:
cn^3-9n = n*(cn^2-9)
= n*c*(n^2-9/c)
= n*c*(n-3/sqrt(c))*(n+3/sqrt(c))
= n*c*(n-n0)*(n+n0)
> 0
(because n>n0>0 , c>0 , n>n0 and n>n0>-n0 )
and therefore
9n < cn^3
which means that 9n in o(n^3) .
上一篇: o（1）代表什么？
下一篇: o符号示例