Question 8 of 8: Complexity

Question 8: Complexity (20 marks: 5 concepts × 4)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

1. Polynomial (P) problem

A problem is in class P if some algorithm solves every instance of size $n$ in time bounded by a polynomial in $n$, i.e. $O(n^k)$ for some fixed constant $k$ — considered "efficiently solvable" in complexity theory. Example: sorting $n$ numbers is in P ($O(n\log n)$, Q5); so is finding a minimum spanning tree ($O(E\log E)$, Q4) and testing whether a number $n$ is prime (AKS primality test, polynomial in the number of digits of $n$).

2. NP problem

NP ("nondeterministic polynomial time") is the class of decision problems for which a proposed certificate (candidate solution) can be verified in polynomial time, even if no polynomial-time method is known to find that certificate in the first place. Every problem in P is also in NP (if you can solve it quickly you can certainly verify a given answer quickly), but whether $P=NP$ — whether finding is always as easy as checking — is the central open question of theoretical computer science. Example: the subset-sum decision problem ("does some subset of these $n$ numbers sum to exactly $T$?") — given a candidate subset, adding it up and comparing to $T$ takes $O(n)$ time, but no polynomial-time algorithm for finding such a subset is known.

3. NP-hard problem

A problem $H$ is NP-hard if every problem in NP can be reduced to $H$ in polynomial time — informally, $H$ is "at least as hard as the hardest problems in NP." NP-hard problems need not themselves be decision problems and need not even be in NP (there may be no way to verify a proposed solution quickly at all); a problem that is both NP-hard and in NP is called NP-complete. Example: the travelling salesman optimization problem ("find the shortest Hamiltonian cycle") is NP-hard — its decision version ("is there a Hamiltonian cycle of length $\le K$?") is NP-complete, and the optimization version is at least as hard since solving it also solves the decision version.

4. Asymptotic complexity vs. worst-case complexity

Asymptotic complexity is a way of describing how a cost (time or space) grows as the input size $n \to \infty$, ignoring constant factors and lower-order terms — expressed with Big-O (upper bound), Big-$\Omega$ (lower bound) or Big-$\Theta$ (tight bound) notation. Worst-case complexity, by contrast, specifies which input is being measured: the maximum cost over all inputs of a given size $n$, as opposed to the best-case (minimum cost) or average-case (expected cost over some input distribution). The two ideas are orthogonal and combine: "worst-case" tells you which scenario you are describing, and "asymptotic" (Big-O/Θ) tells you how that scenario's cost scales with $n$. Example: quicksort's worst-case complexity, expressed asymptotically, is $\Theta(n^2)$ (a badly chosen pivot every time, e.g. an already-sorted array with a first-element pivot), while its average-case complexity is $\Theta(n\log n)$ — same algorithm, two different "which scenario" answers, each stated using the same asymptotic notation.

5. Relation between space and time complexity

Space and time complexity are linked by a general time–space trade-off: extra memory can often be spent to reduce running time, and vice versa. A precomputed lookup table or memoization cache (dynamic programming, Q7.5) converts repeated $O(f(n))$ recomputation into $O(1)$ lookups at the cost of $O(n)$ or more extra storage; conversely, an algorithm can be made to use less memory by recomputing values on demand instead of storing them, at the cost of extra time. As a hard theoretical bound (not just a design heuristic), a Turing machine running in time $f(n)$ can only ever visit $O(f(n))$ distinct memory cells, so $\text{TIME}(f(n)) \subseteq \text{SPACE}(f(n))$ — an algorithm can never use more space than the number of steps it takes. Example: computing the $n$-th Fibonacci number recursively without memoization is $O(2^n)$ time but only $O(n)$ space (call-stack depth); memoizing it (or the simple iterative version) drops the time to $O(n)$ by spending $O(n)$ space to remember prior results.