Functions with logarithmic time complexity, noted $O(\log n)\,$ will run and return their output in an amount of time that depends only on the number of elements in the tree.

When a k-d tree is properly balanced, inserting a new element in the tree takes logarithmic time operation, since the tree only need to be walked down once: from the root node to the leaf, to find the position were to insert the new element.