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

Costs by data structure

A table worth remembering.

The common ones

Array: index O(1), search O(n), insert in the middle O(n). Linked list: insert at a known point O(1), index O(n). Hash map: insert, lookup and delete O(1) average.

  • Balanced tree: O(log n) for lookup, insert and delete, and it keeps order.
  • Heap: O(1) to see the smallest, O(log n) to remove it.

Choosing one

Pick by the operation you do most. Frequent lookups by key want a hash map, ordered range queries want a tree, and a queue of pending work wants a deque or a heap.