Group 7: Complexity
This group of topics relate to the trade-offs between different ways of measuring the cost of a function or algorithm.
Different ways of measuring cost can be useful in different contexts. Thinking about what each type of cost metric tells us (and what it doesn't tell us!) is important, because it helps us decide on the best way to compare alternative solutions to the same problem.
Topics
You will know that you have achieved this group of learning objectives when you are able to
- Goal 7A: Measuring Cost:
- Explain the benefits and limitations of empirical testing, counting operations, and asymptotic analysis as ways to measure cost.
- Goal 7B: Asymptotic Complexity:
- Compare and contrast \( \mathrm{o}() \), \( \mathrm{O} \), \( \Theta() \), \( \Omega() \), and \( \omega() \), including identifying which to use to describe specific operations.
- Goal 7C: Complexity Analyses:
- Explain the difference between the following analyses:
- Best case
- Expected case
- Worst case
- Perform these analyses on uncomplicated algorithms.
- Explain the difference between the following analyses:
- Goal 7D: Amortized Bounds:
- Explain the meaning of an amortized complexity bound.
Need More Practice?
This group of goals are addressed in the following places:
- Week 7 Lesson 2 (Goal 7A, Goal 7B, Goal 7C)
- Week 10 Lesson 1 (Goal 7D)
(When logged in, completion status appears here.)