Functions with linear time complexity, noted $O(O(n)\,$ , will return their output in an amount of time proportional to the number of element in the tree.

It's a very hard target to reach for most k-d tree algorithms, due to the nature of the tree, but some functions that may use arrays underneath may be able to reach it.