Frequently Asked Questions

Big-O describes how the running time (or memory use) of an algorithm grows as the input size grows, ignoring constant factors and lower-order terms. O(n) means the work scales linearly with input size; it doesn't tell you the exact number of operations, just the growth pattern.

Because Big-O describes growth rate, not exact speed. An algorithm that does 3n operations and one that does 100n operations are both O(n) — they scale identically as n grows, even though one has a bigger constant factor. The constant matters for real-world speed, but not for the asymptotic classification.

O(n) means work grows proportionally to input size — double the input, roughly double the work. O(n²) means work grows with the square of input size — double the input, roughly quadruple the work. For small n the difference can look tiny; for large n it becomes enormous (n = 10,000 gives 10,000 operations for O(n) vs. 100,000,000 for O(n²)).

Not necessarily for small inputs — an O(1) algorithm with a huge constant factor can be slower than an O(n) algorithm on small n. Big-O only describes what happens as n grows large; it says nothing about performance at any single fixed size. For large enough n, though, O(1) will always eventually win.

Time complexity measures how the number of operations grows with input size. Space complexity measures how the memory used grows with input size. They're analyzed with the same Big-O tools but are independent — an algorithm can have great time complexity and poor space complexity, or vice versa.

Every recursive call adds a frame to the call stack that stays allocated until that call returns. A recursive function whose calls are all live at once — like one that recurses once per element — uses O(n) stack space. A recursive function that halves its problem each call, like binary search, only ever has O(log n) frames active at once.

Some algorithms, like quicksort, perform very differently depending on the input's structure. A poor pivot choice on already-sorted input can make quicksort degrade to O(n²), even though its average case across random inputs is O(n log n). Algorithms like merge sort avoid this by making the same amount of work regardless of input order.

It helps to recognize the common classes on sight (O(1), O(log n), O(n), O(n log n), O(n²), O(2ⁿ)), but the more valuable skill is being able to derive them from code — counting loops, recognizing halving patterns, and multiplying nested work. That derivation process is the same every time.

Start with How to Analyze Time Complexity of Any Algorithm for the general method, or the Big-O Cheat Sheet for a quick reference across all the common complexity classes. For the distinction between O, Ω, and Θ notation specifically, see Big-O vs. Big-Theta vs. Big-Omega.