Big‑O notation describes the upper bound of an algorithm's time or space complexity as the input size (n) grows. It abstracts away constant factors and focuses on the growth rate. This helps developers compare algorithms independent of hardware, programming language, or implementation details. For example, an O(n²) sorting algorithm will become 100× slower than an O(n log n) one when n grows from 10 to 1000.

O(n!) — factorial time — grows faster than exponential. By n=20, n! ≈ 2.43×10¹⁸ operations. If each operation takes 1 microsecond, that's over 77,000 years of computation. Algorithms with O(n!) complexity (like brute‑force Traveling Salesman Problem) are only practical for very small inputs (n ≤ 12). This is why heuristics and approximation algorithms are essential for NP‑hard problems.

While both are exponential or worse, O(n!) grows much faster than O(2ⁿ). At n=10: 2¹⁰=1,024 vs 10!=3,628,800 (3,500× larger). At n=20: 2²⁰≈1 million vs 20!≈2.4×10¹⁸ (2.4 trillion times larger). O(2ⁿ) algorithms can handle n≈30-40 with care; O(n!) algorithms struggle beyond n≈12-15.

O(log n) means the algorithm divides the problem in half (or by another constant factor) each step. Binary search is the classic example: searching 1 billion sorted items requires only ~30 comparisons. Logarithmic algorithms scale extremely well — doubling the input size adds just a constant amount of extra work. This is the second-best complexity class after O(1).

Quadratic algorithms like Insertion Sort can be faster than O(n log n) algorithms for small n due to lower constant factors and better cache locality. They're also simpler to implement and have less overhead. Many hybrid algorithms (like Timsort) use O(n²) strategies for small sub‑problems and switch to O(n log n) for larger ones. Always benchmark with real data.

Big‑O gives you the shape of the growth curve, not exact runtime. To estimate: (1) Measure actual runtime for a small n. (2) Calculate the constant factor: c = actual_time / f(n). (3) Predict runtime for larger n: c × f(larger_n). For example, if O(n²) takes 0.01s at n=100 (c=10⁻⁶), then n=10,000 would take ~100 seconds. Use our visualizer's time estimation cards as a rough guide.

For most coding interview problems: O(n log n) or O(n) is the expected time complexity. O(n²) is usually a "brute force" baseline that you should improve upon. O(2ⁿ) solutions (like generating all subsets) are acceptable only when explicitly required. Always state the complexity of your solution and discuss trade‑offs between time and space.

Big‑O (O): Upper bound — "at most this fast." Big‑Omega (Ω): Lower bound — "at least this slow." Big‑Theta (Θ): Tight bound — "exactly this growth rate." When we casually say "O(n log n)" for Merge Sort, we technically mean Θ(n log n). Big‑O is the most commonly used in industry because it describes the worst‑case guarantee that matters for production systems.