How do you know how fast a computer can calculate an answer, or whether an answer can be calculated at all? The field of Computational Complexity is the study of whether problems can be solved, and how fast. This lesson introduces some simple ideas about algorithms and their complexity through a series of exercises involving a collection of socks. Of course, other objects can be used as well. This is an active learning lesson that does not require access to a computer. Linear, polynomial, and logarithmic algorithms are explored building an intuitive understanding of order of magnitude.
11 – 13
- for finding something in a sequence.
- for finding something in an ordered list.
- for simple sorting.
- and provide informal methods for determining algorithm complexity.
Anticipated Learner Outcomes
- describe why finding an item in a collection may require looking at each item.
- discuss that ordering objects significantly reduces the time needed to find a specified one.
- discuss that there are many ways to sort objects.
This lesson introduces some simple ideas about algorithms and their complexity through a series of exercises involving a collection of socks.
Alignment to Curriculum Frameworks
Curriculum alignment sheet is included in PDF.