What is the time complexity of this piece of code?

Question

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.

Answer 1

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)!)$.