Spatial C++ Library
Generic MultiDimensional 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 kd 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 

2  2  2 
3  3  3.50 
4  4  5.04 
8  8  11.53 
16  16  25.40 
32  32  54.72 
64  64  116.30 
128  128  244.86 
1024  1024  2206.14 
1048576  1048576  2846273.17 
In many kd 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.