Time Complexity.
How algorithm performance scales with input size, expressed in Big O notation.
Time Complexity
Measures how running time increases with input size. Helps predict scalability for large datasets.
Space Complexity
Measures memory usage relative to input size. Critical for memory-constrained environments.
Growth Comparison
Complexity Classes
Operations that take the same amount of time regardless of input size.
- Array access by index
- Push/pop on a stack
- Hash table insert
Hash table lookups are typically O(1), making them ideal for frequent access operations.
Runtime grows logarithmically. Common in algorithms that halve the problem each step.
- Binary search
- Balanced BST lookup
- Divide and conquer
Database B-tree indexes use O(log n) lookups, enabling fast searches across millions of rows.
Runtime grows linearly. Each input element requires exactly one pass.
- Linear search
- Array traversal
- Finding min/max in unsorted list
Processing a data stream is at minimum O(n) since every element must be examined.
Common in efficient sorting algorithms that combine linear and logarithmic passes.
- Merge sort
- Heap sort
- Quick sort (average)
Most production sort implementations (including JavaScript's Array.sort) use this class.
Runtime grows with the square of input. Typically caused by nested loops over the data.
- Bubble sort
- Selection sort
- Checking all pairs in an array
A million-item input would require a trillion operations. Avoid for large datasets.
Runtime grows with the factorial of input. Impractical beyond very small inputs.
- Brute-force traveling salesman
- All permutations
- N-queens brute force
With just 20 items, a factorial algorithm would take longer than the age of the universe.
Algorithm Reference
| Algorithm | Category | Best | Average | Worst | Space |
|---|---|---|---|---|---|
| Bubble Sort | Sorting | O(n) | O(n²) | O(n²) | O(1) |
| Selection Sort | Sorting | O(n²) | O(n²) | O(n²) | O(1) |
| Insertion Sort | Sorting | O(n) | O(n²) | O(n²) | O(1) |
| Merge Sort | Sorting | O(n log n) | O(n log n) | O(n log n) | O(n) |
| Quick Sort | Sorting | O(n log n) | O(n log n) | O(n²) | O(log n) |
| Heap Sort | Sorting | O(n log n) | O(n log n) | O(n log n) | O(1) |
| Counting Sort | Sorting | O(n+k) | O(n+k) | O(n+k) | O(n+k) |
| Radix Sort | Sorting | O(nk) | O(nk) | O(nk) | O(n+k) |
| Linear Search | Searching | O(1) | O(n) | O(n) | O(1) |
| Binary Search | Searching | O(1) | O(log n) | O(log n) | O(1) |
| Jump Search | Searching | O(1) | O(√n) | O(√n) | O(1) |
| Interpolation | Searching | O(1) | O(log log n) | O(n) | O(1) |
| BFS | Graph | O(V+E) | O(V+E) | O(V+E) | O(V) |
| DFS | Graph | O(V+E) | O(V+E) | O(V+E) | O(V) |
| Dijkstra's | Graph | O((V+E)log V) | O((V+E)log V) | O((V+E)log V) | O(V) |
| Bellman-Ford | Graph | O(VE) | O(VE) | O(VE) | O(V) |
| Floyd-Warshall | Graph | O(V³) | O(V³) | O(V³) | O(V²) |
| Prim's | Graph | O(E log V) | O(E log V) | O(E log V) | O(V+E) |
| Kruskal's | Graph | O(E log E) | O(E log E) | O(E log E) | O(V+E) |
| Array Access | Data Structure | O(1) | O(1) | O(1) | O(1) |
| Array Search | Data Structure | O(1) | O(n) | O(n) | O(1) |
| Array Insertion | Data Structure | O(1) | O(n) | O(n) | O(1) |
| Hash Table Search | Data Structure | O(1) | O(1) | O(n) | O(n) |
| BST Search | Data Structure | O(1) | O(log n) | O(n) | O(n) |
| AVL Tree Ops | Data Structure | O(log n) | O(log n) | O(log n) | O(n) |
V = vertices, E = edges, k = range of values