Scala Vector的prepend操作复杂度为何是effectively constant(eC)？

Great question—this is a common point of confusion because we're used to thinking about prepend on arrays (which is O(n)). Let's break down why Scala's Vector behaves differently.

• Vector's underlying structure is a trie, not a flat array
  Scala's Vector is implemented as a 32-way trie (a tree where each node has up to 32 children). Elements are stored in leaf nodes, and internal nodes point to child nodes. The depth of this tree is tiny even for massive collections: for example, a Vector holding 2^60 elements only has a depth of 12 (since 32^12 = 2^60).

• Prepend doesn't require moving existing elements
  Unlike an array (where prepend forces every element to shift right), prepending to a Vector only involves creating a small number of new nodes at the top of the trie. Since Vector is immutable, most of the existing trie structure is shared with the new Vector—we don't copy or modify existing elements.
  For example:

  • If the top-level node has empty slots, we just create a new top node with the new element in the first slot, and reuse the rest of the original node's children.
  • If the top-level node is full, we create a new root node, add the new element to one of its slots, and point another slot to the original top-level node.

• "Effectively constant" means logarithmic time with a huge base
  The theoretical time complexity is O(log₃₂ n), but log₃₂ grows extremely slowly. Even for a Vector with 1 billion elements, log₃₂(1e9) is only about 6. That's such a small, fixed number of operations that it's indistinguishable from constant time in practice—hence the term "effectively constant" (eC).

So the key takeaway is that Vector's trie structure lets it avoid the O(n) element shifting that arrays require, and the logarithmic factor is so negligible that it's treated as effectively constant.

内容的提问来源于stack exchange，提问作者Anurag Sharma