Confused on Little O meaning
So what I took from little o page is when you apply the small O notation we have to check if one rate is faster then the other (small o focuses on the upper bound)?
In this case when we apply small o:
2^n = o(3^n) will be false as 2^n and 3^n upper bound is equal in speed but not less then
2n = o(n^2) is true as n^2 upper bound is 2 and 2n does not have an upper bound.
Am I on the right track?
2^n is in o(3^n) (little o), since:
lim_n->infinity (2^n / 3^n) = 0
Simmilarly. for 2n , it is easy to show that it is in o(n^2)
An intuitive for "little o" is - it's an upper bound, but not a tight one. It means, a function f(n) is in o(g(n)) if f(n) is in O(g(n)) , but not in Omega(g(n)) .
In your example, 2^n is in O(3^n) , but it is not in Omega(3^n) , so we can say it is in o(3^n)
the only difference between the big O and Small O is that big O allows the function to grow at equal phase however the small O states that g(x) has higher rate of growth and can never be equal after a specific point x'(considering f(x)=o(g(x)) )
The first example you have provided is wrong as small O states that: for f(x)=o(g(x)) |f(x)|x'
however in the above case where f(x)=2^x and g(x)=3^x there exists no C and x' to satisfy it as g(x) has higher rate of growth.
the best way to define small O if you understand Big O is:
A function is called small O if it is Big O but not Big Omega -- this is because the big omega and big O only intersect at the condition when the rate of groth of both function s is equal so if we remove that specific case it is small O.
However please remember that if f(x) is Big O g(x) it can also be small O of g(x) however vice versa is not possible.
链接地址: http://www.djcxy.com/p/39896.html上一篇: 如果f≠ω（g），那么f = O（g）？
下一篇: 困惑于小O的含义