Big-O notation describes how an algorithm's running time grows with the input size n. The complexities that come up most are binary search at O(log n), merge sort at O(n log n), quicksort at O(n log n) on average but O(n²) in the worst case, and graph traversal at O(V + E).
| Algorithm or operation | Time complexity |
|---|
| Binary search | O(log n) |
| Merge sort | O(n log n) |
| Quicksort | O(n log n) average, O(n²) worst case |
| Bubble sort and insertion sort | O(n²) |
| Hash table lookup | O(1) average |
| Breadth-first and depth-first search | O(V + E) |
| Dijkstra's algorithm with a binary heap | O((V + E) log V) |
Worked example: binary search for 23 in the sorted list [3, 8, 12, 17, 23, 31, 40, 52]. The middle element at index 3 is 17, which is less than 23, so search the right half. The new middle at index 5 is 31, which is greater, so search left. Index 4 holds 23: found in 3 comparisons, matching log₂ 8 = 3. For more practice, see data structures help.