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