the runtime (computational complexity) of perms function?

I am wondering how much is the runtime (computational complexity) of perms function? Please just the computational complexity, I know about memory requirements.

Answer 1

[John D'Errico]

You are mistaking the problem here. The issue will always be allocating sufficient memory, thus, the memory required will be what is important.. Computing the actual permutations is fast, IF you have sufficient memory, and a fast enough computer to access that memory.

However, the purely computational complexity is trivial. It is O(factorial(n)*n), where n is the number of elements to permute. Not surprisingly, that is also the number of elements in the array to be created, and this is a direct measure of the memory required.

That is, there are factorial(n) permutations, each of which is represented by a vector of length n to be stored in memory. Regardless of how you compute the numbers. you need to compute factorial(n) permutations. Therefore the complexity will grow as factorial(n). It matters not how it is cloaked in loops. (Trying to unravel the loops is a task that will only confuse things, if that somehow convinces you that it can do the work more quickly.) And since each permutation is a vector of length n...

That the actual computations are pretty efficient is my initial point, that what matters is not in fact the computational complexity. The real issue lies in how much memory you need to allocate, access, and then fill. And since the amount of memory grows faster than exponentially, the problem becomes the amount of memory, since it is simply filling an array of size factorial(n) by n elements.

Your computer operates in a way that will be linear in the number of elements it needs to stuff. And that number of elements grows as O(factorial(n)*n). Therefore the final overall computational complexity of the result MUST be O(factorial(n)*n).

Answer 2

[Walter Roberson]

You can look inside perms.m to see the private function permsr() -- which is iterative, not recursive like the comments imply.

for nn=2:n
    [...]
    for i = nn-1:-1:1
      [...]
    end
end

nn=2, i = 1, nn=3, i=2:1, nn=4, i=3:1 ... This is symsum(nn-1,nn,2,n) which is going to be like (nn-1)*n/2 loops.

If the operatings being done were scalar, then that would be the result, that the computational complexity is O(n^2). However if you dig further you can see that what is done inside the loop is not linear: it is moving around arrays that are getting larger as you go. You can analyze the code in more detail to figure out the actual complexity.

[Walter Roberson]

We know that n! outputs will be created, so the complexity cannot be less than n!. Now, when we reach the K'th permutation to output, if hypothetically we could create it in a constant number of steps, then the time complexity would be just n!. But we are not outputting something of constant width, we are outputting something of width n, so we need at least n operations to create it. That raises the minimum complexity to at least n!*n and possibly higher.

We can now ask the question: if we know the index into the permutation results, is it possible to compute the content of the permutation in order n operations? Because if we were able to find such a matching then we would have created a lower bound and upper bound that were the same, and so would have proved the bound.

It turns out that Yes, given the permutation index, the content can be computed in order n operations. The trick involves decomposing the index as a number of varying base. I can never seem to recall the exact representation, but it is possible, and you can find algorithms to do the decoding.

Therefore, the upper and lower bound are the same and the time complexity is n!*n.

However, the theoretical time complexity is not what you asked about: you asked about the runtime complexity of MATLAB's perms() function, which might be slower. You can examine the code for it.