[prev] 33 [next]

Big-Oh Rules

  • If f(n) is a polynomial of degree d   ⇒ f(n) is O(nd)
    • lower-order terms are ignored
    • constant factors are ignored
  • Use the smallest possible class of functions
    • say "2n is O(n)" instead of "2n is O(n2)"
      • but keep in mind that, 2n is in O(n2), O(n3), …
  • Use the simplest expression of the class
    • say "3n + 5 is O(n)" instead of "3n + 5 is O(3n)"