Orders of growth of algorithms
Constant, logarithmic, linear, linearithmic, quadratic and exponential growth: ranking them, predicting the effect of doubling n and estimating an execution time.
- 32 cards
- 8 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- On the timeline
- The numbers
- The curves
- Scenarios
- Understand
A few cards from the deck
Order of growth of a cost: what is it?
Show the answer
The shape of the growth of the cost as n gets large, keeping only the dominant term and ignoring multiplicative constants.
3n² + 5n + 2 is of order n². For n = 1000, the term 3n² is 3,000,000 and the others 5002: they hardly matter any more.
Selection sort takes 1 s for 10,000 values. How long for 20,000 values?
4 s2 s2.2 s8 s
Show the answer
4 sThe cost is quadratic: doubling n multiplies the operations by 4. 2 s would be the answer for a linear cost, 2.2 s for a cost in n log n, and 8 s for a cost in n³.
When n doubles, a linear cost is multiplied by … and a quadratic cost by ….
Show the answer
When n doubles, a linear cost is multiplied by 2 and a quadratic cost by 4.
For growth in n: 2n / n = 2. For n²: (2n)² / n² = 4. A logarithmic cost grows by only one unit.