Difference in asymptotic time of two variants of flatten

I am going through the Scala by Example document and I am having trouble with exercise 9.4.2. Here is the text:

Exercise 9.4.2 Consider the problem of writing a function flatten, which takes a list of element lists as arguments. The result of flatten should be the concatenation of all element lists into a single list. Here is an implementation of this method in terms of :\.

def flatten[A](xs: 开发者_如何学运维List[List[A]]): List[A] =
  (xs :\ (Nil: List[A])) {(x, xs) => x ::: xs}

Consider replacing the body of flatten by

((Nil: List[A]) /: xs) ((xs, x) => xs ::: x)

What would be the difference in asymptotic complexity between the two versions of flatten?

In fact flatten is predefined together with a set of other userful function in an object called List in the standatd Scala library. It can be accessed from user program by calling List.flatten. Note that flatten is not a method of class List – it would not make sense there, since it applies only to lists of lists, not to all lists in general.

I do not see how the asymptotic time of these two function variants are different. I'm sure it's because I am missing something fundamental about the meaning of fold left and fold right.

Here is a pdf of the document I am describing: http://www.scala-lang.org/docu/files/ScalaByExample.pdf

I am generally finding this an excellent introduction into Scala.

Look at the implementation of concatenation ::: (p.68) (the rest of answer is masked with spoiler-tags, mouse-over to read !)

Witness that it's linear (in ::) in the size of the left argument (the list that ends up being the prefix of the result).

Assume (for the sake of the complexity analysis) that your list of lists contains n equal-sized small lists of size a fixed constant k, k<n. If you use foldLeft, you compute:

f (... (f (f a b1) b2) ...) bn

Where f is the concatenation. If you use foldRight:

f a1 (f a2 (... (f an b) ...))

With again f standing for the prefix notation of concatenation. In the second case it's easy : you add k elements at the head each time, so you do (k*n cons).

For the first case (foldLeft), in the first concatenation, the list (f a b1) is of size k. You add it on the second round to b2 to form (f (f a b1) b2) of size 2k ... You do (k+(k+k)+(3k)+... = k*sum_{i=1}^n(i) = k*n(n+1)/2 cons).

(Followup question : is this the only parameter that should be taken into account while thinking of the efficiency of that function ? Doesn't foldLeft have an advantage -not asymptotic complexity- that foldRight doesn't ?)