Is getting the length of a Sequence a constant-time operation?

Question

I have a Sequence that I want to get the length of:

val x = (1 to 1000000)
x.length

Is this an O(1) operation? (Seems like it, from trying out a couple lines in the repl.) Why? What is a Sequence storing that makes this an O(1) operation, if it is one? (Does it just store the length of the sequence as metadata?)

Answer 1

(1 to 1000000) creates a Range object (not the more general Seq). Range defines length by calling count:

def count(start: Int, end: Int, step: Int, isInclusive: Boolean): Int = {
  // faster path for the common counting range
  if (start >= 0 && end > start && end < scala.Int.MaxValue && step == 1)
    (end - start) + ( if (isInclusive) 1 else 0 )
  else
    NumericRange.count[Long](start, end, step, isInclusive)
}

So, you can see that in the simple case given, a Range with a step size of 1, length is O(1) because it just subtracts end-start and adds one. The NumericRange.count option is more complex, but still uses mathematical operations to find the value in constant time.

As for other Seq types:

List is a linked-list and does not store length information directly, so it requires traversing the entire structure and keeping track of how many elements it sees:

def length: Int = {
  var these = self
  var len = 0
  while (!these.isEmpty) {
    len += 1
    these = these.tail
  }
  len
}

On the other hand, something like Vector stores index information, so it can return the length in constant time:

def length = endIndex - startIndex

Other Seq types may implement length in other ways.

Answer 2

It depends on the implementation of Seq. Length is defined as abstract ( http://www.scala-lang.org/api/current/scala/collection/Seq.html ), so some sequences might be constant time (like arrays), some might be linear (linked lists).