Big-O Complexity Visualizer & Cheat Sheet
Interactive Big-O asymptotic curve simulator and complexity reference table. Slide N to watch how constant, logarithmic, linear, quadratic, and exponential operations diverge at scale.
Rule 1: Always Consider Worst Case
When evaluating scalability, Big-O measures the asymptotic upper bound. For example, linear search in an array of N items might find the item at index 0 (Best Case: O(1)), but Big-O is strictly O(N) because in the worst case, the item is at the very end or missing entirely.
Rule 2: Remove Constants
Constant factors do not affect the rate of growth as N approaches infinity. O(2N) becomes O(N). O(100N + 500) becomes O(N). O(1 + N/2 + 100) becomes O(N). Whether a loop runs twice or once per item, its complexity is strictly linear.
Rule 3: Different Terms for Different Inputs
If an algorithm processes two distinct collections (e.g. array1 of size A and array2 of size B), nested loops result in O(A * B), NOT O(N²). Sequential loops over both arrays result in O(A + B), NOT O(N). Never conflate distinct input dimensions.
Rule 4: Drop Non-Dominant Terms
In multi-stage algorithms with combined polynomial terms, only the fastest-growing term matters at scale. O(N² + 5N + 100) simplifies to O(N²), because as N grows to 1,000,000, the N² term (10¹²) completely dwarfs 5N (5*10⁶).
| Data Structure | Access | Search | Insertion | Deletion | Worst Space |
|---|---|---|---|---|---|
| Array | O(1) | O(N) | O(N) | O(N) | O(N) |
| Stack (LIFO) | O(N) | O(N) | O(1) | O(1) | O(N) |
| Queue (FIFO) | O(N) | O(N) | O(1) | O(1) | O(N) |
| Singly Linked List | O(N) | O(N) | O(1) at head | O(1) at head | O(N) |
| Doubly Linked List | O(N) | O(N) | O(1) at ends | O(1) at ends | O(N) |
| Hash Table | N/A | 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) |
| Algorithm | Best Time | Average Time | Worst Time | Worst Space |
|---|---|---|---|---|
| Merge Sort | O(N log N) | O(N log N) | O(N log N) | O(N) |
| Quick Sort | O(N log N) | O(N log N) | O(N²) | O(log N) |
| Heap Sort | O(N log N) | O(N log N) | O(N log N) | O(1) |
| Bubble Sort | O(N) | O(N²) | O(N²) | O(1) |
| Insertion Sort | O(N) | O(N²) | O(N²) | O(1) |
| Selection Sort | O(N²) | O(N²) | O(N²) | O(1) |