MEPX
Chapter 3 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 3 of 12

Constant and linear time

O(1) and O(n), the two you meet most.

Constant time

O(1) means the work does not depend on the input size. Reading an array by index, pushing onto a stack and looking up a hash map key are all constant on average.

  • Constant does not mean fast, it means unchanging as n grows.
  • A hash lookup is O(1) average and O(n) in the worst case with heavy collisions.

Linear time

O(n) means one pass. Summing a list, finding a maximum and searching an unsorted array are all linear, and you cannot do better when every item must be looked at.