Model answer
From slowest to fastest growth: log n, n, n log n, n², 2ⁿ, n!. Constant factors can affect small inputs, but not this eventual ordering.
Use the key terms, then explain the reasoning.
Algorithm Analysis
C++17
C++17Complexity Classes
Complexity classes group problems and algorithms by resource growth: constant, logarithmic, linear, linearithmic, polynomial, exponential, and factorial.
What to understand
- Growth-rate ordering
- Polynomial versus exponential
- P and NP intuition
- Feasible input sizes
Remember this
- 1log n grows very slowly
- 2n log n is typical for efficient comparison sorting
- 3Exponential algorithms become impractical quickly
Detailed notes
Growth classes predict how quickly resource demands explode. Doubling n barely affects logarithmic work, doubles linear work, roughly doubles-plus-one-pass linearithmic work, and quadruples quadratic work.
P and NP classify decision problems rather than individual programs. P contains problems solvable in polynomial time; NP contains problems whose proposed solutions can be verified in polynomial time. Whether P equals NP remains unknown.
How it works
- 1Order classes from constant through factorial growth.
- 2Estimate operation counts at realistic values of n.
- 3Separate problem complexity from a particular algorithm's complexity.
- 4Identify when constraints permit exponential or pseudo-polynomial methods.
Where it is used
- Selecting feasible approaches from input limits
- Recognising when heuristics or approximation may be required
- Planning performance and capacity tests
Common mistakes
- Assuming every polynomial algorithm is practically fast
- Calling an optimisation problem NP without defining a decision form
- Ignoring key-range parameters in pseudo-polynomial algorithms
Implementation perspective
This is primarily a conceptual or selection topic. Use the linked implementation topics in this section to see the invariant expressed in C++.
Exam & viva
Open a prompt when you are ready to check your answer.