Time and Space Complexity of Leetcode Problem #31. Next Permutation
The number of calls indeed grows slower than \$n*n!\$. Its growth is only \$O(n!)\$. However, number of calls is not the only source of complexity. 

Constructing arguments for the recursive call also takes time, and rem[:i] + rem[i + 1:] is on average linear in terms of n. The total complexity therefore is \$O(n*n!)\$, just as some people say.