What is the time complexity of Ruby's built in #permutation and #repeated_permutation methods?

Question

I've been wondering about the time complexity of some of Ruby's built-in methods, these two in particular. I think the best I've been able to come up with for a permutation method on my own is Θ(n · n!), does Ruby's built-in perform better? If so, please help me understand their algorithm.

Answer 1

Permutation

Array#permutation returns an Enumerator with n! Arrays, so the time complexity will be at least O(n!).

I wrote this method :

def slow_method(n)
  (1..n).to_a.permutation.each do |p|
    p
  end
end

It doesn't do anything with p, expect forcing the generation of all the permutations. Building an Array of all the permutations would use too much memory.

This method was called 10 times for n between 10 and 13, and the average times in seconds were :

t10 = 0.618895
t11 = 6.7815425
t12 = 82.896605
t13 = 1073.015602

O(n!) looks like a reasonable approximation :

t13/fact(13)*fact(12)/t12 #=> 0.995694114280165
t13/fact(13)*fact(11)/t11 #=> 1.0142685297667369
t13/fact(13)*fact(10)/t10 #=> 1.0103498450722133

O(n*n!) doesn't :

t13/(fact(13)*13)*fact(12)*12/t12 #=> 0.9191022593355369
t13/(fact(13)*13)*fact(11)*11/t11 #=> 0.8582272174949312
t13/(fact(13)*13)*fact(10)*10/t10 #=> 0.777192188517087

The generation seems to be O(n!), but doing anything with the generated Arrays would bring the overall complexity to O(n*n!).

Why isn't the generation O(n*n!)? It could come from the fact that when recursively generating [1,2,3,4,5].permutation, the remaining permutations are the same for [1,2] and [2,1].

O(n!) is already so slow that n will never be much bigger than 10, so O(n*n!) isn't much worse. For n=20, n! is 2432902008176640000 and n*n! is 48658040163532800000.

Repeated Permutation

[1,2,...n].repeated_permutation(k) generates n**k Arrays of k elements.

The complexity should be either O(n**k) or O(k*n**k).

For k=n, it becomes O(n**n) or O(n**(n+1)), which is even (much) worse than for permutation.