2

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?

Community
  • 1
  • 1
S A
  • 827
  • 10
  • 23
  • You'll probably get better answers if you ask this on http://cs.stackexchange.com/ – Ewan Mellor Dec 28 '15 at 19:01
  • I'm voting to close this question as off-topic because it belongs on cs.stackexchange.com. – Kurt Revis Dec 28 '15 at 19:13
  • @KurtRevis I am more focused on algorithm and programming. This could also be in cs but could also be in stack over flow. I am just trying to be better at programming and computational. Sadly, I am not studying or learning computer science (I am self learning), I have just googled "effective programming" and came across this, which is a small part to cs and the whole of the programming industry. – S A Dec 28 '15 at 19:18

2 Answers2

4

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)

amit
  • 175,853
  • 27
  • 231
  • 333
  • I kind of understood that. Are trying to say 2^n = o(3^n) is true? Because In the link that is provided it has to be less then with small o and with big O it could be less then or equal to... Im just confused sorry. – S A Dec 28 '15 at 19:20
  • @SA since `lim_{n->infinity} (2^n/3^n) = 0`, `2^n` is NOT in `Omega(3^n)`. and since it is also in `O(3^n)`, we can conclude it is in `o(2^n)`. – amit Dec 28 '15 at 20:31
1

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.

Yashwin Gokavarapu
  • 21
  • 2