Big-O for everyday data structures

Inline math and code mixed into plain text — e.g. a hash map lookup is $O(1)$ on average and you call it with map.get(key).

Arrays and lists

• Index access a[i]: $O(1)$
• Search unsorted: $O(n)$ · search sorted (binary search): $O(\log n)$
• Insert at end (dynamic array): amortised $O(1)$ · insert at front: $O(n)$

Hash maps

• Get / put / delete: $O(1)$ average, $O(n)$ worst case when everything collides.

Trees and heaps

• Balanced BST search / insert / delete: $O(\log n)$
• Heap push / pop: $O(\log n)$ · peek: $O(1)$

Sorting

• Merge sort, heap sort: $O(n \log n)$ always.
• Quick sort: $O(n \log n)$ average, $O(n^2)$ worst.
• Counting sort: $O(n + k)$ when keys are small integers.

Growth at a glance

For $n = 10^6$: $\log n \approx 20$, $n \log n \approx 2 \times 10^7$, $n^2 = 10^{12}$ — the difference between milliseconds and days.