I was reading this for calculating permutation of numbers https://keaoxu.files.wordpress.com/2018/08/permutation_output_algo_analysis.pdf where a backtracking solution time complexity is presented.
Below is the algorithm from the paper
Below is the time complexity analysis
How is the lower bound calculated for this?
You can do this by showing sum of $x!$ where $x\le n$, is $\le e\cdot n!$ $\implies$ $$\begin{align}n \displaystyle\sum_{i=0}^{n-1} \prod_{n-i}^{n} &= n\cdot n! \sum_{i=0}^{n-1} \left(\frac{1}{n!}\prod_{n-i}^{n}\right)\\&=n\cdot n! \sum_{i=0}^{n-1} \frac{1}{(n-i-1)!}\\ &= n\cdot n! \sum_{i=0}^{n-1} \frac{1}{i!} \\&\le n\cdot n! \cdot e\\\\&=O(n\cdot n!)\end{align}$$