Functions with quasilinear time complexity, noted $O(n (\log n)^{1/k})\,$ 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 $T(n) = O(n (\log n)^{1/3})\,$ 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 $O(n)\,$	Quasilinear Time $T(n) = O(n (\log n)^{1/3})\,$
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 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.