The Ruby on Rails experts

May 26, 2013

This stackoverflow answer does a great job in illustrating Big O notation for algorithm complexity. The author has a use case related to phone books for each level of complexity:

  • O(1) – Given the page number and the person’s name, find the person’s phone number. [Comment by JH: I find this one weak because it assumes constant time for looking up a page number, when in reality is’s more like log(n). A better example would be to find a random person’s phone number by flipping open any page in the phone book].
  • O(log n) – Given a person’s name, find the corresponding phone number (This is a binary search for a person’s phone number).
  • O(n) – Find all people whose phone numbers contain the digit “5″.
  • O(n log n) – Sort a phone book’s pages by looking at the first name on each page.
  • Read the original article for higher complexity examples:  algorithm – What does O(log n) mean exactly? – Stack Overflow via stackoverflow.com