Complexity of the algorithm that generates permutations

0
votes

I have trouble understanding how you get to determine the time complexity of this algorithm (written in Python, but would suit any language):

def permutazioni(list):
    n = len(list)
    if n == 1 or n == 0: 
        return [list]
    else:
        risult = []
        for i in range(n):
            primo = list[i]
            listaDegliAltri = list[:i] + list[i + 1:]  
            perms = permutazioni(listaDegliAltri)
            for perm in perms:
                risult.append([primo] + perm)
    return risult

This procedure takes as input a sequence and returns as a result a sequence of sequences containing the set of all possible permutations of the starting sequence.

Example: permutations([a, b, c]) = [[a, b, c], [a, c, b], [b, a, c], [b, c, a], [c, a , b], [c, b, a]]

Now, to determine the complexity, I have to write and solve the equation of recurrence. When the list is long 0 or 1, no operations are performed. Otherwise, you run a cycle of n iterations in which each iteration the function is called on a list with one element shorter than (n-1) and then you run an inner for long n-1.

The professor then wrote:

T(0) = T(1) = 1 (1 why? Is it the cost of the return or other?)

T(n) = n*(T(n-1) + (n-1)) for n>1

Then he says that chooses the lower boundary and then writes (hereafter I did not understand anything):

T(n) > n*T(n-1)

from which:

T(n) > nT(n-1) > n(n-1)T(n-2) > n(n-1)*(n-2)*T(n-3)> ... > n!

That is:

T(n) = Ω(n!)

I did not understand because it has eliminated the (n-1) and because it has put the major instead of the equal sign. So I didn't understand anything. Someone explain it to me would know? Thank you

2
algorithmtime-complexitypermutation

2 Answers

0
votes

Your professor should have probably written T(0) = T(1) = Theta(1) meaning that it takes constant time for these cases, but just putting a fixed constant like 1 usually doesn't change the asymptotics. As for the rest, if you believe that 

T(n) = n*(T(n-1) + Theta(n-1))

(again I have put big-Theta to emphasize that there may be hidden constant multipliers when you count operations), then you obviously get that

T(n) > n*T(n-1)

because you have subtracted the positive term Theta(n-1). The rest follows by the definition of factorials.

0
votes

This is just a great deal of error prone but very basic algebra.

The reason M(1) and M(0) are 1 is because if you have a list with 1 or zero elements, then the list is itself its only permutation. For instance {1} only has one permutation, and so does {}. So the 1 has nothing to do with work done per se, but really there is only one permutation. But also it is true that you simply return it, so you can think of it like that.

Now for the more interesting/boring part.

If you accept

T(0) = T(1) = 1

T(n) = n*(T(n-1) + (n-1)) for n>1

Then the rest is tedious algebra. So tart by saying that T(n-1)=T(k). So

T(n) = n*((k*(T(k-1) + (k-1))) + (n-1))

T(n) = n*(((n-1)*(T(n-1-1) + (n-1-1))) + (n-1))

T(n) = n*((k*(T(n-2) + (n-2))) + (n-1))

T(n) = n^3 + n^2*T(n-2) - 2n^2-n*T(n-2)+n: this is just algebraic expansion.

If you replace T(n-2) and then T(n-3) with T(k), you will see the factorial patern emerge, namely that n! = n*(n-1)!