title: How is the time complexity of building k-d tree O(nlog^2n) when O(nlog(n)) median search is used?
body: <p>The time complexity of building a k-d tree using O(nlogn) meidan search is given as O(nlog^2n) in <a href="https://www.wikiwand.com/en/K-d_tree" rel="nofollow noreferrer">wikipedia</a>. Can anybody explain how it is O(nlog^2n)?</p>