Algorithm complexity – easy understanding
Written on 23 May 2013, 05:02pm
Tagged with: algorithms
O(1) – Time to complete is the same regardless of the size of input set. An example is accessing 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 scales linearly with 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 is counting the 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 is heap sort and quick sort.
O(N^2) – Time to complete is roughly equal to the square of the number of items. An example of this is bubble sort.
O(N!) – Time to complete is the factorial of the input set. An example of this is the traveling salesman problem brute-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. (n moving 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: 264)