Discussion prompt
20 minutes. Think of a task you do (sorting mail, searching files, matching names) that would become much slower if the amount grew a hundred times. In 150 to 200 words, say whether the extra work would be linear or quadratic, and why.
Private: nothing you type here is sent or stored.
This course has no discussion board yet, so the prompt is a private reflection.
Recap
- Cost is a count of basic steps written in terms of n.
- Constant, logarithmic, linear and quadratic growth: doubling n leaves, adds a step, doubles or quadruples the cost.
- Compare methods at your real n; growth rate decides in the long run.
- Exponential growth doubles per extra item and soon becomes impractical.
Module notes
Key terms. Input size: the amount of data (n). Basic step: one simple action. Growth rate: how cost changes as n grows. Crossover: the n at which two methods cost the same. Trade-off: gaining one quality at the expense of another.
Rules and formulas. Adding n numbers: n − 1 additions. Pairs among n items: n × (n − 1) ÷ 2. Subsets of n items: 2 to the power n.
Limits of this module. This module counts idealised steps for simple methods. Real timing depends on hardware and data, and a formal treatment of growth is left to later study.
Next
Continue to Module 6: Abstraction, Functions and Structure. You can also return to the course overview or the University Track.
References and further reading
- Specialty Digest encyclopedia: Algorithm, Computer and Programming Language.
- The growth rates of searching, sorting and subset checking are standard textbook results.
- Methods A, B, P and S and all scenario figures in this module are invented for teaching and labelled as such.