The teacher shows three ways to find a value in an unsorted list of a million records: a linear search, sorting the list then using binary search, and building a hash table then looking the value up. Students vote on Mentimeter twice, once for the best method for a single lookup and once for ten thousand lookups, each with a one-line Big O justification. The teacher looks at both splits, and if many chose binary search for the single lookup, asks two students to set the cost of sorting first, O(n log n), against a single O(n) scan. Students vote again on the single-lookup question, then in pairs write the total cost of each method for k lookups as an expression.
Tools: Mentimeter Nine ideas for your own version in Generate
This page is one of a growing set of PICRAT examples by cell, subject and grade. Page maintained by Andy Perryer.