Time & Space Complexity Analysis (Big-O)
Asymptotic Complexity Analysis uses Big-O, Big-Omega, and Big-Theta notation to bound an algorithm's runtime and memory growth as input size n scales, guiding algorithm selection from input constraints.
Difficulty: Easy · Interactive Visualizer · C++ / Python / Java / JS Code
Time & Space Complexity Analysis (Big-O)
Asymptotic Complexity Analysis measures how an algorithm's operations and memory scale as input size $n \to \infty$, ignoring hardware-dependent constant factors:
- $O(f(n))$ (Big-O): Asymptotic upper bound (worst case).
- $\Omega(f(n))$ (Big-Omega): Asymptotic lower bound.
- $\Theta(f(n))$ (Big-Theta): Asymptotic tight bound (both $O$ and $\Omega$).
Constraint-to-Complexity Cheat Sheet (~$10^8$ Ops / Second)
| Input Size $n$ | Max Acceptable Complexity | Typical Algorithms |
| :--- | :---: | :--- |
| $n \le 12$ | $O(n!)$ | Permutations, N-Queens |
| $n \le 20$ | $O(2^n \cdot n)$ | Bitmask DP, Subsets |
| $n \le 500$ | $O(n^3)$ | Floyd–Warshall, Matrix Chain |
| $n \le 5{,}000$ | $O(n^2)$ | 2D DP (LCS, Edit Distance) |
| $n \le 10^5$ | $O(n \sqrt{n})$ | Sqrt Decomposition, Mo's Algorithm |
| $n \le 10^6$ | $O(n \log n)$ or $O(n)$ | Merge Sort, Segment Tree, BFS/DFS |
| $n \le 10^{18}$ | $O(\log n)$ or $O(1)$ | Binary Search, Fast Exponentiation, Digit DP |
---
Amortized Analysis Example: Dynamic Array Doubling
Even though resizing a std::vector copies $n$ elements in $O(n)$ worst case, doubling capacity ($1, 2, 4, \dots, n$) copies
Loading AntInLoop...
push_back!
<details>
<summary>Show C++ Demonstration</summary>
#include <iostream>
int main() {
int cap = 1, copies = 0, n = 1024;
for (int sz = 0; sz < n; ++sz) {
if (sz == cap) { copies += cap; cap *= 2; }
}
std::cout << "Total copies for " << n << " appends: " << copies
<< " (< 2*n, amortized O(1)!)\n";
return 0;
}
</details>
---
Related Algorithms
- Master Theorem — closed-form complexity for divide-and-conquer recurrences.
- Mathematical Proofs — proving correctness and bounds.