Determining order class of $T(n) = nT(n-1) + n$ with $T(1) = 1$

Question

I'm trying to solve the following problem:

Define $T(n) = n\cdot T(n-1) + n$ with $T(1) = 1$. Is $T(n) \in \mathcal O(2^n)$?

I started by finding the time complexity of $T(n) = n\cdot T(n-1) + n$ and I got something weird:

$$n!\cdot\left(\frac{1}{n!} + \frac{1}{(n-1)!} + \cdots + \frac{1}{(n-n)!}\right)$$

I found this by drawing a tree and simplifying the expression I got, but it doesn't really make sense.

Answer 1

Suppose that $T(n)=\Theta (2^n)$. Then your recurrence would become $$Θ(2^n) = n\cdot\Theta(2^n-1) + n = n\cdot \Theta(2^n)$$ ...which is false.

Your explicit formulation is actually more informative. If you reverse what's in the parentheses, you can write it as: $$\frac{1}{0!}+\frac{1}{1!}+\frac{1}{2!}+\cdots+\frac{1}{n!}$$

As $n$ grows, this converges to $e$ (which means that we can bound it by a constant). So you've found that $T(n)=\Theta(n!)$, which does agree with your recurrence.

Answer 2

Just let us see what we get if we expand $T(n) = n⋅T(n-1) + n$:

\begin{align}T(n) &= n⋅T(n-1) + n\\ &= n⋅((n-1)⋅T(n-2) + n-1) + n\\ &= n⋅((n-1)⋅((n-2)⋅T(n-3) + (n-2)) + (n-1)) + n\\ &= n⋅(n-1)⋅(n-2)⋅T(n-3) + n⋅(n-1)⋅(n-2) + n⋅(n-1) + n\\ &= \sum_{k=1}^n \frac{n!}{k!} \end{align}

Since $n!$ is a summand of this sum and with $n! \approx \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$ (see Stirling's approximation), we know

$$\lim_{n\to\infty} \frac{n!}{2^n} \approx \lim_{n \to\infty} \frac{\sqrt{2\pi n}\left(\frac{n}{e}\right)^n}{2^n} = \frac{n^n}{(2e)^n} \to \infty$$

So there does not exist any constant $c$ to fulfill $T(n) \leq c\cdot 2^n$ for every $n \geq n_0$, so $T(n)$ cannot be in $\mathcal O(2^n)$. Or in other words: $T(n)$ is in $\omega(2^n)$.

Notice: I ignored the biggest part of the sum, but to show that $T(n)$ is not in $\mathcal O(2^n)$, we don't have to look at the whole sum, but only on this part, that is big enough to see that $T(n)$ is not in $\mathcal O(2^n)$.

An easier approach: $T_1(n) = n⋅T_1(n-1) + n$ is greater than $T_2(n) = n\cdot T_2(n-1)$, so if $T_2(n)$ is not in $\mathcal O(2^n)$, this holds for $T_1(n)$ too.