I believe time complexity is O(n^2) since there is one iteration through the input for which index to examine, and a second iteration, placing the character at each position of the input to generate various combinations. Therefore, n x n. Do X for each time of Y.

https://www.geeksforgeeks.org/time-complexity-permutations-string/