Thinking About Speed: Big O
An algorithm is a step-by-step method for solving a problem. A data structure is a way of storing data so an algorithm can work with it well. The two go together: the right structure often turns a slow method into a fast one.
To compare methods we ask how the work grows as the input grows. This is called Big O notation.
| Big O | Name | Example |
|---|---|---|
| O(1) | constant | read items[0] |
| O(log n) | logarithmic | binary search |
| O(n) | linear | look at every item once |
| O(n log n) | linearithmic | good sorting |
| O(n squared) | quadratic | compare every pair |
We count steps, not seconds, so the answer does not depend on how fast your computer is. The example counts the steps of two ways of finding a duplicate.
A method takes twice as many steps when the input doubles. What is its Big O?
Count how many comparisons the nested loop makes for a list of 10 items (each pair once) and print the count.
Finish the quick check (and any code exercise) to complete this lesson, or mark it done yourself.
Tip: use the left and right arrow keys to move between lessons.