O(1)– Time to complete is the same regardless of the size of input set. An example isaccessing an array element by index.

O(Log N)– Time to complete increases roughly in line with the log2(n). binary search /divide and conquer

O(N)– Time to complete that scaleslinearlywith the size of the input set. In other words if you double the number of items in the input set, the algorithm takes roughly twice as long. An example iscountingthe number of items in a linked list.

O(N Log N)– Time to complete increases by the number of items times the result of Log2(N). An example of this isheap sortandquick sort.

O(N^2)– Time to complete is roughly equal to the square of the number of items. An example of this isbubble sort.

O(N!)– Time to complete is the factorial of the input set. An example of this is thetraveling salesman problembrute-force solution.

And the Phone book example:

O(1): Given the page that a person’s name is on and their name, find the phone number.

O(log n): Given a person’s name, find the phone number by picking a random point about halfway through the part of the book you haven’t searched yet, then checking to see whether the person’s name is at that point. Then repeat the process about halfway through the part of the book where the person’s name lies. (This is a binary search for a person’s name.)

O(n): Given a phone number, find the person or business with that number (reverse look up).

O(n log n): There was a mix-up at the printer’s office, and our phone book had all its pages inserted in a random order. Fix the ordering so that it’s correct by looking at the first name on each page and then putting that page in the appropriate spot in a new, empty phone book. (nmoving pages *log(n)comparisons in the new address book)For the below examples, we’re now at the printer’s office. Phone books are waiting to be mailed to each resident or business, and there’s a sticker on each phone book identifying where it should be mailed to. Every person or business gets one phone book.

O(n log n): We want to personalize the phone book, so we’re going to find each person or business’s name in their designated copy, then circle their name in the book and write a short thank-you note for their patronage.(n books, log n for names search)

O(n^2): A mistake occurred at the office, and every entry in each of the phone books has an extra “0” at the end of the phone number. Take some white-out and remove each zero.(n books, n names)

**Update**: Big O Cheatsheet.com/

*Written by*
**Dorin Moise**
(Published articles: 231)

- Likes (
*0*) -
Share
- Comments (0)