Complexity of recursive permutation algorithm

Question

I'm reading Richard Bird's Algorithm design with Haskell, in section 2.2, he considers the following algorithm to calculate the list of permutations of a list:

perms = foldr (concatMap · inserts) [[]]
inserts x [] = [[x]]
inserts x (y : ys)=(x : y : ys):map (y:) (inserts x ys)

Then he concludes the recurrence relation for T (perms running time) to be

T(n+1) = T(n) +n!(I(n) +Θ(n^2))

With the justification

The function I(n) is the time to compute the list of insertions of a new element in a permutation of length n. There are n+1 results, each of which is a list of length n+1, and it takes Θ(n^2) to concatenate them. Finally, there are n! permutations of a list of length n, so the insertions are computed n! times.

My question is why does the term Θ(n^2) appear? I tried to follow the book method, and expanded the definition using explicit recursion

perms []=[[]]
perms (x:xs)=concatMap.inserts x foldr (concatMap.inserts) [[]] xs

So, we have T(n) (the time required to find the permutations of the tail represented by the foldr term in the recursion), now using I(n) with the above definition, it is the cost of mapping the inserts x over a single element of foldr (concatMap.inserts) [[]] xs, which produces a list of n+1 lists (the there are n+1 possible indices for insertion) each list contains n+1 elements (a permutation of length n with one more element), what I don't understand is the need to concatenate those n+1 lists, since the concatenation operation is done on the result of map as a whole, not mapped over every inserts x output, that is we have

concat.map (inserts x) [L_1,L_2,...,L_(n!)], where each L_i has length n and represents a permutation of n elements.

=concat [ inserts x L_1,inserts L_2,....]

=concat [ LL_1,LL_2,...,LL_(n!)] where each LL_i is a list of n+1lists [P_(i,1),P_(i,2)...,P(i,n+1)] with each P_(i,j) having n+1 elements.

So the concatenation is is applied to the list

[ LL_1,LL_2,...,LL_(n!)]=[P_(1,1),P_(1,2)...,P(1,n+1),P_(2,1),P_(2,2)...,P_(n!,n+1)]

The book previously computes the complexity of the concat xss to be Θ(mn) with m=length xss consisting of lists each with length n, my analysis gives the recurrence relation

T(n+1)=T(n) + n!*I(n) + Θ(n!*(n+1)), Is this correct?

Edit

To be more clear, from the recursive definition,

T(n) is the cost to calculate the permutations of length n.
I(n) is the cost to perform a single inserts x operation, multiplied by the number of times it will be done, which gives n!*I(n)
Θ(n!*(n+1)) is the complexity of the concat.

user_3768871 · Answer

It depends on the list manipulation in Haskell. As you can find in this document, as an example, when you concatenate to arrays, the concatenation cost is at least to copy elements of the minimum length array. Hence, if concatenation is implemented efficiently, at least in each concatenation of n lists with the size of n+1, we have the cost of n copy. Hence, the time complexity of the concatenation of n+1 lists with the length of n is in Theta(n^2).

user_7203016 · Answer

It looks to me like Bird has made a mistake and you are correct. Yes, each of the n! insertions creates a list of n+1 results, each of which is a list of n+1 elements, but Bird's description appears to make it clear that he is imagining, for each result, the concatenation of the n+1 lists of n+1 elements into a single list of elements requiring O(n^2) time for each of the n! results, when it is only the outer list of n! lists of n+1 lists that must be concatenated into a length n!*(n+1)=(n+1)! list of lists of elements.

Concretely, in computing permutations of [1,2,3], it takes T(2) to compute:

[[2,3],[3,2]]

and it takes I(3) each for the 2! insertion results:

[[1,2,3],[2,1,3],[2,3,1]]
[[1,3,2],[3,1,2],[3,2,1]]

However, concatenating these does not require an O(3^2) operation for each insertion result; it only requires concatenating the 2! insertion results themselves, each of length 3, previously established as an O(2!*3) or simply O(3!) operation.

So, you're right that it should read:

T(n+1) = T(n) + n!I(n) + O((n+1)!)

This doesn't appear in the list of errata so maybe you should send an email to the address listed on that page and see if he agrees.

Complexity of recursive permutation algorithm

2 Answers