map reduce complexity

Question

Lets suppose that i have this input: a list of list

(def list-of-list-3 (list (list 1 2 3) (list 4 5 6) (list 7 8 9)) )

(map #(reduce * %1) list-of-list3 )

The map-reduce has a O(n^2) complexity in this case?

is map-reduce translated as two nested for ?

So when i run the above example on the clojure REPL, the complexity time seems like O(n).

when i duplicate the input size ( list-of-list-6 (list (list 1 2 3) (list 4 5 6) ( list 7 8 9) (list 8 2 3) (list 9 8 1) (list 7 6 4)) ) the time increase in a linear way, not quadratic.

Can anyone say why ?

thanks in advance

Answer 1

The map-reduce has a O(n^2) complexity in this case?

Impossible to say, unless you tell us what n corresponds to in the list-of-list-3 expression.

By the way, O(n^2) or O(n*n) is quadratic complexity, not exponential complexity. Exponential complexity it O(e^n).

when i [double] the input size

( list-of-list-6 (list (list 1 2 3) (list 4 5 6) ( list 7 8 9) 
                       (list 8 2 3) (list 9 8 1) (list 7 6 4)) )

the time increase in a linear way, not exponential.

From this, I surmise that the n is supposed to be the length of the outer list. If so, then the reduce is actually O(n) not O(n^2). To get quadratic growth, you would need to define list-of-list-6 as:

( list-of-list-6 (list (list 1 2 3 4 5 6) (list 4 5 6 1 3 2) 
                       (list 7 8 9 1 2 3) (list 8 2 3 2 3 4) 
                       (list 9 8 1 2 3 4) (list 7 6 4 5 6 7)) )

Answer 2

It's not O(n^2), it's roughly O(n*m) where n is the no of lists and m is the length of them. There will be other factors as well to do with the lengths of various numbers. Do it by hand and time yourself to see why!