Re:Sublinear Time Algorithms
by Aurornis on Monday February 24, 2025 @12:09PM
(#43162007)
Binary search requires a sorted input, which requires that you first consider all elements of the input data set.
The sublinear algorithms this page is discussing require that the algorithm not consider all elements of the data set and you're not allowed to pre-process it with an O(n) or greater algorithm.
So no trees, no binary search. It's a different set of algorithms.
The sublinear algorithms this page is discussing require that the algorithm not consider all elements of the data set and you're not allowed to pre-process it with an O(n) or greater algorithm.
So no trees, no binary search. It's a different set of algorithms.