O(n*n*n!) = O((n+2)!)

Question

I am going through a programming time complexity learning os a recursive function to find all the combinations of the given string. This is stated by the author. I am trying to figure out how n*n*n! == (n+2)!

O(n*n*n!) = O((n+2)!)

Answer 1

You have two very different things in your question. It is not true that $n*n*n!=(n+2)!$. It is true that $O(n*n*n!) \in O((n+2)!)$ because $(n+2)!=(n+2)(n+1)n!=n^2n!+$terms like $n\cdot n!$ and $n!$ where the later terms are ignorable. The big O notation hides a lot of things. It is only interested in the leading term.

Answer 2

One of the simpler or more intuitive definitions for the big $\mathcal O$ notation is this: $f(x) \in \mathcal O (g(x))$ if and only if

$$\limsup_{x \to \infty} \left| \frac{f(x)}{g(x)} \right| < \infty$$

(It need not be $\infty$ but that's likely the relevant point for your application.) Then, notice two things. First, this does not necessitate $f=g$; it's a characterization of growth rate. Next, we see by applying the definition of factorial that

$$\begin{align} \frac{n \cdot n \cdot n!}{(n+2)!} &= n^2 \cdot \frac{n(n-1)(n-2)\cdots(2)(1)}{(n+2)(n+1)(n)(n-1)(n-2)\cdots(2)(1)} \\ &=\frac{n^2}{(n+2)(n+1)} \end{align}$$

When you see this simplification, the limit $n \to \infty$ is obviously $1$ since the bottom is also a quadratic in $n$, allowing you to reach the desired conclusion.

Thus, this means that whenever $f \in \mathcal O (n^2n!)$ we also have $f \in \mathcal O((n+2)!)$.