MEPX
Chapter 6 of 12All chapters
  1. 1Why complexity matters
  2. 2Reading Big O
  3. 3Constant and linear time
  4. 4Logarithmic time
  5. 5Sorting and its floor
  6. 6Quadratic and worse
  7. 7Best, average and worst
  8. 8Space complexity
  9. 9Amortised analysis
  10. 10Costs by data structure
  11. 11Recursion and recurrences
  12. 12Choosing an algorithm

Chapter 6 of 12

Quadratic and worse

Nested loops, and when they are acceptable.

O(n squared)

Comparing every item with every other item is quadratic. At a thousand items that is a million operations, which is fine. At a million items it is a trillion, which is not.

  • Bubble sort, insertion sort and naive duplicate finding are all quadratic.
  • A hash set usually turns a quadratic search into a linear one.

Beyond quadratic

O(2 to the n) and O(n factorial) appear in brute force over subsets or orderings. They are usable only for tiny n, which is why these problems get approximations.