Spatial C++ Library
Generic Multi-Dimensional Containers and Spatial Operations
Functions with quasilinear time complexity, noted will return their output in an amount of time mostly proportional to the number of elements being considered, although their running time will still grow faster than pure linear time complexity, however it is still very close to it.
For example, considering a perfectly balanced k-d tree, iterating through all elements in the tree takes roughly regardless of the number of dimensions, and for any number of elements. To help you compare, below is a table that gives order of execution time:
|Number of Elements||Linear Time||Quasilinear Time|
In many k-d tree operations involving the retreival of several elements from the tree, walking up and down the nodes in the tree is a necessary operation. Therefore it is a desirable time complexity to reach, because it's the upper barrier for most of these algorithms.