生成字符串所有排列的函数的时间复杂度是多少（来自破解代码面试）

Question

function addChar(arrStrings, desiredChar) //O(nm^2) where n is the length of arrStrings and m is the length of each string in arrayStrings.          
{
    const resultStrings = [];
    for(let i = 0; i < arrStrings.length; i++) 
    {
        //currString is the array of character representation of each string in arrStrings
        let currString = [...arrStrings[i]];
        for(let j = 0; j <= currString.length; j++) //number of positions that we can insert desiredChar in, it's equal to the length of the string
        {
            //tempString is a copy of the array of characters currently being worked on in arrStrings. We want modify this instead of currString
            let tempString = [...currString];
            tempString.splice(j,0,desiredChar)
            //push the modified tempString in the form of a string by using join()
            resultStrings.push(tempString.join(""));
        }
        
    }
    return resultStrings;
}


function generatePermutations(s)
{
    //base case: this means the input is the answer
    if(s.length === 1)
        return [string];

    //Generate permutations for the string without the last character. Store that in an array of strings
    const removeLastChar = s.slice(0,s.length - 1);
    const permOneLessChar = generatePermutations(removeLastChar);
    //store the last character of the string
    const desiredChar = s[s.length - 1];

    //return an array of strings where the last character in s is inserted in each of the strings in permOneLessChar at every position
    return addChar(permOneLessChar, desiredChar);
}

上面的代码返回一个字符串数组，其中包含一个字符串的所有排列。它通过找到没有最后一个字符的字符串的所有排列，然后在这些排列中的每个位置插入最后一个字符来实现。 addChar 是一个辅助函数，它在每个索引位置处的字符串数组中的所有字符串中插入指定字符。本解法来自破解代码面试。 addChar 的时间复杂度为 O(nm^2)，其中 n 是字符串数组的长度，m 是数组中每个字符串的长度。假设数组中每个字符串的长度相同。如果有人能对整个程序的时间复杂度做出有根据的猜测，我将不胜感激。