Algorithm Efficiency CS Thinking Example 2
Follow the full solution, then compare it with the other examples linked below.
Example 2
hardExplain why binary search () is more efficient than linear search () for a sorted list of 1,000,000 elements.
Solution
- 1 Step 1: Linear search checks each element one by one: up to 1,000,000 comparisons in the worst case.
- 2 Step 2: Binary search halves the search space each step: comparisons.
- 3 Step 3: Binary search is roughly 50,000 times faster for this input size.
Answer
Binary search needs ~20 comparisons vs 1,000,000 for linear search. vastly outperforms .
Logarithmic algorithms are extremely efficient because they eliminate half the remaining data each step. This is why keeping data sorted enables much faster searching.
About Algorithm Efficiency
The ratio of useful output energy (or power) to total input energy, expressed as a percentage — always less than 100% due to energy losses.
Learn more about Algorithm Efficiency →More Algorithm Efficiency Examples
Example 1 hard
Algorithm A takes 100 steps for an input of size 10 and 400 steps for size 20. Algorithm B takes 10
Example 3 hardRank these time complexities from most to least efficient: [formula], [formula], [formula], [formula
Example 4 hardAlgorithm X checks every pair of students in a class of size `n`. Algorithm Y checks each student on