This recurrence basically comes from the typical solution to N-queens problem. Some people say the complexity is O(n) while giving recurrence T(n) = n(T(n−1) + n). But from what I can tell, this concludes O((n+1)!), which is surely different from O(n!) asymptotically.
By induction,
If T(k) <= ck!,
Then, T(n) <= n*c(n-1)! + n*n = cn! + n*n. Thus we don't have T(n) <= cn!.
On the other hand,
If T(k) <= c(k+1)!,
Then, T(n) <= n*cn! + n*n <= n*cn! + cn! = c(n+1)!.
Is this correct? If so, what's the correct way to prove it(other ways than induction is also OK)?
Let $U(k)=\frac{T(k)}{k!}$. Then $$U(n)=U(n-1)+\frac{n}{(n-1)!}=U(n-1)+\frac1{(n-1)!}+\frac1{(n-2)!}\\ <U(1)+2e-1\\ T(n)<2e(n!)$$