3 ms·
Data structured as trees permit a lot of sublinear operations. Set intersection for example, you traverse the two trees in the same order, and where a node exis
by JonChesterfield 2y ago
Data structured as trees permit a lot of sublinear operations. Set intersection for example, you traverse the two trees in the same order, and where a node exists in one and not the other, you know nothing under it is in the intersection.
- Aurornis 2y agoIn this case, Sublinear Algorithms refers to algorithms that don't consider the entire input set. A B-Tree would not qualify because it must first consider the entire input set. Only later operations can be less than O(n) because you've already done O(n) or greater work on the data set.