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