Practice question · Multiple choice
Binary search is O(log n) and needs sorted data; a linear scan is O(n) and needs nothing. For a list searched once, which wins?
Hints
- Add up the total cost of each approach for one search, including any preparation.
- Ask how many searches you would need before the sort pays for itself.
Show the answer
B. The linear scan, since sorting first costs more than it saves
Why
Sorting to save one scan is a loss: O(n log n) to avoid O(n). The crossover comes at roughly log n searches, after which the preprocessing is repaid many times, which is the same calculation that decides whether a database should build an index or just scan the table.
Practise Computational Complexity
The app has 5 more questions on this lesson, and keeps your place in the course. Mathematics I is free to start.
More questions on Computational Complexity
- Select every statement about big-O notation that is TRUE.
- Match each complexity class to an operation that has it.
- Order these complexity classes from the slowest-growing to the fastest-growing.
- A quadratic algorithm takes 4 seconds on an input of size 1000. Assuming the quadratic model holds, roughly…
- Binary search halves the remaining portion of a sorted list at each step. Starting from 1024 items, how many…
- Complete the description of big-O notation.
- An O(n²) algorithm can beat an O(n log n) one on real data. Why does big-O notation not settle which program…