3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Is T (n) greater than n factorial ? $\endgroup$ – gnasher729 Jan 23 '15 at 12:22
  • $\begingroup$ What is 1 / (n - n)! ? $\endgroup$ – gnasher729 Jan 23 '15 at 12:23
  • $\begingroup$ @gnasher729 1/(n-n)! is 1 divided by the factorial of n-n=0, and basically I'm trying to find the time complexity of the T(n)=nT(n-1) + n so I can check if it's O(2^n) $\endgroup$ – jtht Jan 23 '15 at 12:48
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ @anorton Thanks for the edit. My answer was migrated from Stackoverflow where latex doesn't work. $\endgroup$ – AbcAeffchen Jan 29 '15 at 5:22
  • 1
    $\begingroup$ No problem; I keep my eye out for migrated questions and edit them to use TeX if I like the question/answers. $\endgroup$ – apnorton Jan 29 '15 at 5:23
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.