Scala Vector operations aren't "Effectively Constant" time

[manuzhang]

Article

• http://www.lihaoyi.com/post/ScalaVectoroperationsarentEffectivelyConstanttime.html

Notes

• The author acknowledges the following things are true

  • Vector operations take O(log32(n)) time
  • it never takes more than 6 steps to perform an operation on the Vector given the max size of machine integer on JVM is 2^31.

• The author argues the "Effectively Constant" claim is incorrect

  • O(log32(n) is O(0.2log32(n)) is O(log2(n))
  • real effect is irrelevant in asymptotic Big-O analysis and Vector is not very fast actually
  • n should go to infinity in Big-O analysis not 2^31. (wrong ?)
  • if considering n < 2^31 in Big-O analysis, then O(log2(n) is also "effectively constant"
  • if constant factor matters in Big-O analysis, then 5 "effectively constant" operations becomes logarithmic. So does translating a logarithmic operation from Python to Java