Talk:Ball tree

time complexity

What is "time complexity $O(n\,lg\,n)$?" Is it $O(n\log n)$? Kkddkkdd (talk) 15:29, 22 April 2015 (UTC)

Qeustion(1) wrt. above: why should there be an interpreation-difference wrt. "lg(..)" vs "log(..)", ie, as both are used (among others in Copmtuer-science) to abbreviate the "logarithm(..)" term? (oekseth)

Qeustion(2): First impression is that $log_{2}$ is used, ie, simliar to typical kd-tree implementastiions: anyone who have read library-soruce-codes validating latter assumption? — Preceding unsigned comment added by 82.164.65.143 (talk) 22:54, 17 May 2017 (UTC)

Asymptotically, all logarithms are the same. The base is just a constant factor that is ignored by theoretical complexity analysis (although constant factors make a big difference in reality, as our data is finite). 77.177.132.161 (talk) —Preceding undated comment added 11:08, 10 December 2017 (UTC)