Re:Scala Vector operations aren't “Effectively Constant” time
by rrobukef on Thursday August 10, 2017 @02:14AM
(#14976938)
I don't think they should use effectively constant. Because the difference between O(1) and O(log(n)) may not be very big but the difference between O(n) and O(n log(n)) is very measurable. Even for small n.
The 32-way tree operations have asymptomic complexity 6 * C_1 * log(n) = C_2 * log(n)
Operations on a balanced binary tree have asymptotic complexity C_3 * log(n) = 6 * C_4 * log(n).
The only difference between the two data structures is the actual values of the constants.
I think the Scala people have a valid point that logarithmic complexity may be as good (or nearly as good) as constant-time in practice. The precise way the claim is formulated is wrong and abuses big-O analysis.
A more correct argument is to choose a practical upper bound on log(n). E.g. maybe 64. Then multiply that by the constant factor (not playing any tricks with splitting out 6 *). If that number is always good enough if practice, then you don't need to worry about your operation being logarithmic.