Practice question · Numerical answer
Binary search halves the remaining portion of a sorted list at each step. Starting from 1024 items, how many halvings reduce it to a single item?
Hints
- Ask what power of 2 gives 1024.
- 1024, 512, 256, ... keep going and count.
Show the answer
10
Why
, so ten halvings suffice. This is why logarithmic algorithms are so powerful: a thousandfold increase in data costs only ten extra steps.
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 is O(log n) and needs sorted data; a linear scan is O(n) and needs nothing. For a list searched…
- 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…