Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Order Notation Assumptions Clarification
#1
On the page called order: beastie.cs.ua.edu/cs201/order.html it seems to say that we should only ignore constant factors and other lower order terms when dealing with Big Omega, Theta, and Big Omicron. Is it true that that is not assumed when dealing with Little Omega and Little Omicron?

In other words, should I consider lower order terms and constant factors with Little Omega and Little Omicron?
Reply
#2
Technically, speaking, lower order terms and constants wouldn't affect little omega or little omicron. For example:

if f is n^2 + n + 3 and g is n^3 + 5, then f = o(g)

This is true because n^2 +n + 3 grows more slowly than n^3 + 5. On the other hand, n^2 + n + 3 grows more slowly than n^2 +2n + 5. But we consider those growth rates equal because the n^2 dominates. To make things cleaner looking, we remove the constants and lower order terms in *all* are asymptotic equations, including little omega and little omicron.
Reply


Forum Jump:


Users browsing this thread: 1 Guest(s)