Rank the Big-Os
Put these running times in order from slowest-growing (best for large inputs) to fastest-growing:
O(n2), O(1), O(n log n), O(2n), O(log n), O(n), O(n!)
Show hint
Try n = 1,000 in your head. How big is each one, roughly?
Show solution
O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O(2n) < O(n!)
- O(1): reading a list item by index.
- O(log n): binary search.
- O(n): one pass over the data.
- O(n log n): a good sort.
- O(n2): comparing every pair.
- O(2n): trying every subset.
- O(n!): trying every ordering.
Want a problem like this every day? See today's problem and keep a streak going.