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)