Algorithm Efficiency CS Thinking Example 4
Follow the full solution, then compare it with the other examples linked below.
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`.
Solution
- 1 Step 1: Checking every pair means nested comparisons, so Algorithm X is `O(n^2)`. Checking each student once is a single pass, so Algorithm Y is `O(n)`.
- 2 Step 2: For n = 1000, quadratic growth is much larger than linear growth, so Algorithm Y scales far better as the class size increases.
Answer
Algorithm X is `O(n^2)` and Algorithm Y is `O(n)`. Algorithm Y scales much better for large inputs.
Efficiency is about how quickly work grows as the input grows. An algorithm that is acceptable for small inputs can become unusably slow if its growth rate is too high.
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 2 hardExplain why binary search ([formula]) is more efficient than linear search ([formula]) for a sorted
Example 3 hardRank these time complexities from most to least efficient: [formula], [formula], [formula], [formula