Source: https://dsc40b.com/materials/lectures/02-time_complexity-pt_I/slides-marked.pdf
Design an algorithm for the following problem
Given the heights of
people, what is the height of the tallest doctor you can make by stacking two of them?
Brute force solution
- Loop through all possible (ordered) pairs
- Check height of each
- Keep the best
Linear Time
Quadratic Time
Linear growth: if input size doubles, time roughly doubles
Quadratic growth: if input size doubles, time roughly quadruples
Exponential growth: increasing input size by one doubles (or triples, quadruples, etc.) time taken
Example: brute force search of
Logarithmic growth: to increase time taken by one unit, must double (triple, etc.) input size