algorithmbig-otime-complexitycomputer-sciencelittle-o

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?


Solution

  • 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)