map reduce complexity

1
votes

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

2
clojurecomplexity-theoryjvm-languages
It would be a good idea to remove 'java' from the tag list. The implementation looks like a LISP variant. – David Weiser
Yeah David, i will. This variant is called Clojure, another JVM Language. Its really cool ! My next languages will be scala or clojure. :D – CHAPa

2 Answers

4
votes

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!

2
votes

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)) )