Algorithms
Algorithm complexity
Big-O notation reference, sorting algorithm comparison.
Big-O Complexity Classes
| Notation | Name | Growth | n=10 | n=100 | n=1,000 | Example |
|---|---|---|---|---|---|---|
O(1) | Constant | • | 1 | 1 | 1 | Array index, hash lookup |
O(log n) | Logarithmic | •• | 3 | 7 | 10 | Binary search, balanced BST |
O(n) | Linear | ••• | 10 | 100 | 1,000 | Linear search, single loop |
O(n log n) | Linearithmic | •••• | 33 | 664 | 9,966 | Merge sort, Heap sort, FFT |
O(n²) | Quadratic | ▲▲▲▲▲ | 100 | 10,000 | 1,000,000 | Bubble sort, nested loops |
O(n³) | Cubic | ▲▲▲▲▲▲ | 1,000 | 1,000,000 | 10⁹ | Matrix multiplication (naive) |
O(2ⁿ) | Exponential | ⬛ | 1,024 | 10³⁰ | 10³⁰¹ | Recursive Fibonacci, subsets |
O(n!) | Factorial | ⬛⬛ | 3,628,800 | 9×10¹⁵⁷ | — | Permutations, brute-force TSP |
Sorting Algorithms
| Algorithm | Best | Average | Worst | Space | Stable | Note |
|---|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Simple, slow |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | No | Minimum swaps |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | Yes | Good for small / nearly sorted |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | Guaranteed, extra memory |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) | No | Fast in practice, pivot matters |
| Heap sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | In-place, not cache-friendly |
| Tim sort | O(n) | O(n log n) | O(n log n) | O(n) | Yes | Python & Java default sort |
| Counting sort | O(n+k) | O(n+k) | O(n+k) | O(k) | Yes | Integer keys only |
| Radix sort | O(nk) | O(nk) | O(nk) | O(n+k) | Yes | Non-comparison, fixed digits |
| Shell sort | O(n log n) | O(n^1.3) | O(n²) | O(1) | No | Gap-based insertion |
Data Structure Operations
| Structure | Access | Search | Insert | Delete | Space |
|---|---|---|---|---|---|
| Array | O(1) | O(n) | O(n) | O(n) | O(n) |
| Linked List | O(n) | O(n) | O(1) | O(1) | O(n) |
| Hash Table | — | O(1) avg | O(1) avg | O(1) avg | O(n) |
| Binary Search Tree | O(log n) avg | O(log n) avg | O(log n) avg | O(log n) avg | O(n) |
| AVL Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(n) |
| Trie | O(k) | O(k) | O(k) | O(k) | O(n·k) |
| Graph (adj. list) | O(V+E) | O(V+E) | O(1) | O(E) | O(V+E) |
k = key length, V = vertices, E = edges, n = elements. avg = average case.