Iterators concatenation performance

Question

Just below, the code of Iterator's ++ method:

/** Concatenates this iterator with another.
       *
       *  @param   that   the other iterator
       *  @return  a new iterator that first yields the values produced by this
       *  iterator followed by the values produced by iterator `that`.
       *  @note    Reuse: $consumesTwoAndProducesOneIterator
       *  @usecase def ++(that: => Iterator[A]): Iterator[A]
       */
      def ++[B >: A](that: => GenTraversableOnce[B]): Iterator[B] = new Iterator[B] {
        // optimize a little bit to prevent n log n behavior.
        private var cur : Iterator[B] = self
        // since that is by-name, make sure it's only referenced once -
        // if "val it = that" is inside the block, then hasNext on an empty
        // iterator will continually reevaluate it.  (ticket #3269)
        lazy val it = that.toIterator
        // the eq check is to avoid an infinite loop on "x ++ x"
        def hasNext = cur.hasNext || ((cur eq self) && {
          it.hasNext && {
            cur = it
            true
          }
        })
        def next() = { hasNext; cur.next() }
      }

In comment, it says: // optimize a little bit to prevent n log n behavior..

When and how would concatenating two iterators lead to n log n ?

Answer 1

By popular demand, I answer to my own question, quoting the @Paolo Falabella comment just above:

It's mentioned in "Programming in Scala 2nd ed.". The log n is due to the extra indirection introduced by having to decide at each step of the iteration if the next element comes from the first or the second iterator.