Loading...
Complexity describes how required resources grow with problem size. It is a model of scaling rather than a stopwatch prediction for one computer.
What you'll be able to do
Choose the relevant problem-size measure: number of array items, graph vertices and edges, or the number of bits in an encoded value. State which operations are treated as constant-cost. A numerical loop bound and the number of digits used to represent that bound are not identical input-size measures.
A mathematical function maps a domain to a co-domain. Growth functions such as n, n², 2ⁿ and log n model different scaling patterns. Big-O expresses an asymptotic upper bound; teaching labels usually use a useful tight order, rather than an unnecessarily loose bound.
A single pass over n items gives linear work under the model. Two full independent nested n-iteration loops give n² body executions. Sequential linear passes add, so 3n+n remains O(n), not O(n²). Repeatedly halving a positive candidate range gives logarithmic iterations.
A loop that runs from 1 through n and performs i operations on its ith pass totals n(n+1)/2, still quadratic. A merge-sort decomposition performs linear work across logarithmically many levels. Trace the bounds and dependencies rather than counting the written number of loops alone.
Worst-case, best-case and average-case claims describe different input assumptions. A linear search is constant in its best case but linear in its worst. Space complexity measures storage, which can differ from time; retaining every intermediate state may increase space even if the final answer is short.
Polynomial time includes constant, logarithmic and ordinary nᵏ bounds for fixed k. Exponential 2ⁿ eventually outgrows fixed-degree polynomials. There are n! permutations of n distinct objects, another rapidly growing search space. Faster hardware changes constants but does not remove the underlying growth pattern.
| n | n² | 2ⁿ |
|---|---|---|
| 4 | 16 | 16 |
| 8 | 64 | 256 |
| 16 | 256 | 65,536 |
Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.
Common mistakes to avoid
Key takeaways
Test yourself
Answer a few questions, then review anything you missed.
Start with the quiz above to check the key ideas. You can also choose another topic from the practice library.