0
$\begingroup$
def find_perms(s):
    """
    Finds permutations of the given string.
    >>> find_perms("abc")
    ['cab', 'acb', 'abc', 'cba', 'bca', 'bac']
    """
    if len(s) == 1:
        return [s]
    elif len(s) == 2:
        return [s[0]+s[1], s[1]+s[0]]
    else:
        perm = find_perms(s[0:len(s)-1])
        last_char = s[len(s)-1]
        lst = []
        for strings in perm:
            for index in range(len(strings)+1):
                string = strings[:index] + last_char + strings[index:]
                lst.append(string)
        return lst

I am trying to figure out the time complexity of this piece of code as I'm working on studying coding questions and their time complexity and I managed to solve this permutation problem using recursion as was required but I am wondering how do I accurately determine the big-$O$ time complexity for this as it is a mix of recursion followed by an iterative loop. I would really appreciate some helpful input on this.

$\endgroup$

1 Answer 1

0
$\begingroup$

Let $f(n)$ be the answer for an input of size $n$. then we have the following equation:

$f(n) = f(n - 1) + (n - 1)! * n = f(n - 1) + n!$

That's because you call the function for an input of size $n - 1$ which gives $f(n - 1)$, then you iterate over all permutations of size $n - 1$ which there are $(n - 1)!$ such permutations, and then you iterate over the position of the new element, which there are $n$ such positions. This gives us:

$f(n) = [\sum_{i=1}^n i!] < (n + 1)!$

You can easily prove this by induction. So $f(n) = O((n + 1)!)$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.