Big-O notation describes how the running time or space requirement of an algorithm grows as the input size n increases. It expresses an upper bound on the growth rate, ignoring constant factors and lower-order terms - only the dominant term matters as n becomes large. O(1) (constant) is the best case: execution time doesn't change regardless of input size.
O(n) (linear) doubles when input doubles. O(n²) (quadratic) quadruples when input doubles.
Understanding Big-O lets you compare algorithms objectively and predict performance at scale. An O(n log n) sort like Merge Sort will always outperform an O(n²) sort like Bubble Sort for large datasets, even if the latter has smaller constant factors. Space complexity applies the same notation to memory usage.
The distinction between worst-case, average-case, and best-case complexity is also important: Quick Sort is O(n log n) on average but O(n²) in the worst case with a bad pivot choice.
Understanding Big-O Complexity Cheat Sheet
Big O is based on counting the main operations an algorithm performs, rather than timing one run on one computer. A comparison, assignment, or array access can be treated as one small unit of work. This model is not perfectly realistic, since real processors, memory caches, and programming languages have different costs.
It is still useful because it reveals the pattern that remains when the data becomes very large. Two programs can have the same growth class yet feel very different on small inputs.
A program with more setup work may lose on ten items but win on ten million. Big O gives a long term prediction, not a stopwatch reading.
Reading code for complexity requires care. Two loops do not automatically mean quadratic work. If one loop runs through a list and another runs through a separate small fixed set, the total can still grow linearly.
A nested loop becomes quadratic when both loops can grow with the input size. A loop that repeatedly cuts a remaining range in half has logarithmic growth, even if it contains several simple operations. Conditional statements matter too.
An early exit can make a search very fast for some inputs, while an item near the end requires much more work. The shape and order of the input can therefore affect the case being measured.
Space complexity includes more than the data stored in a final answer. It includes temporary arrays, helper tables, recursive function calls, and copies made while processing data. Recursion uses call stack memory for each unfinished call.
A recursive method can be easy to read but may fail on a very deep input if the stack is limited. Some algorithms use extra memory to avoid repeated work. For example, storing results of smaller subproblems can turn an extremely slow recursive calculation into a manageable one.
This is a common tradeoff. Less time often costs more memory, while saving memory can require repeating calculations.
Students meet these ideas when searching contacts, sorting game scores, loading social media feeds, or processing sensor readings. A slow method may be harmless in a homework program with twenty values, yet cause delays or high cloud costs with millions of records. When analysing an algorithm, first define what counts as the input size.
For a graph, it may be the number of vertices plus the number of connections. For a string task, it may be the number of characters. Then identify the work that repeats as the input grows.
Write down loop bounds, recursive calls, and stored data. Finally, test with larger inputs when possible. Measurements catch real world costs that growth analysis deliberately leaves out.
Key Facts
- O(1): constant time - array index lookup, hash table access
- O(log n): halves the problem each step - binary search, balanced BST operations
- O(n): linear - linear search, single-pass array traversal
- O(n log n): divide-and-conquer sorts - Merge Sort, Heap Sort, Quick Sort (average)
- O(n²): nested loops - Bubble Sort, Insertion Sort, Selection Sort
- O(2ⁿ): exponential - brute-force subset enumeration; impractical for n > ~30
Vocabulary
- Big-O notation
- A mathematical notation describing the upper bound on an algorithm's growth rate, expressed as a function of input size n.
- Time complexity
- The number of basic operations an algorithm performs as a function of input size; measured in Big-O notation.
- Space complexity
- The amount of memory an algorithm uses as a function of input size, including both auxiliary and input storage.
- Worst-case complexity
- The maximum running time of an algorithm over all possible inputs of size n; what Big-O typically expresses.
- Amortized complexity
- The average time per operation over a sequence of operations, allowing some operations to be more expensive than others (e.g. dynamic array resizing).
Common Mistakes to Avoid
- Ignoring constant factors and lower-order terms. O(2n) and O(n) are the same class - Big-O drops constants. But in practice, constant factors matter at small n; use profiling for real optimization.
- Assuming a better Big-O always means faster in practice. An O(n log n) algorithm with high constant overhead can be slower than an O(n²) algorithm for small n. Profiling beats theoretical analysis for small inputs.
- Confusing worst-case with average-case. Quick Sort is O(n²) worst case but O(n log n) average case. Always specify which case you mean.
- Forgetting space complexity when evaluating algorithms. Merge Sort is O(n log n) time but O(n) space. In memory-constrained environments, an in-place O(n²) sort may be preferable.
Practice Questions
- 1 What is the Big-O time complexity of finding an element in a sorted array using binary search? Explain why.
- 2 Nested loops each running n times give O(n²). What is the complexity of three nested loops each running n times, and give an example algorithm with this complexity.
- 3 Quick Sort has O(n²) worst-case but O(n log n) average-case complexity. Describe the worst-case input that triggers O(n²) behavior.