Practice Algorithm Efficiency in CS Thinking
Use these practice problems to test your method after reviewing the concept explanation and worked examples.
Quick Recap
The ratio of useful output energy (or power) to total input energy, expressed as a percentage — always less than 100% due to energy losses.
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`.