Practice Algorithm Efficiency in CS Thinking
Use these practice problems to test your method after reviewing the concept explanation and worked examples.
Quick Recap
Algorithm efficiency describes how an algorithm's time or memory requirements grow relative to the size of its input, measured using Big O notation. It answers the question: as the input gets larger, how much slower does the algorithm become?
Does doubling the data double the time? Or quadruple it? Or barely change it?
Example 1
hardAlgorithm A takes 100 steps for an input of size 10 and 400 steps for size 20. Algorithm B takes 10 steps for size 10 and 20 steps for size 20. Which is more efficient and what might their time complexities be?
Example 2
hardExplain why binary search (O(\log n)) is more efficient than linear search (O(n)) for a sorted list of 1,000,000 elements.
Example 3
hardRank these time complexities from most to least efficient: O(n^2), O(1), O(n \log n), O(n), O(2^n).
Example 4
hardAlgorithm X checks every pair of students in a class of size `n`. Algorithm Y checks each student once. Match each algorithm to `O(n^2)` or `O(n)`, and explain which scales better for `n = 1000`.