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$
3
  • 1
    $\begingroup$ Is T (n) greater than n factorial ? $\endgroup$
    – gnasher729
    Jan 23, 2015 at 12:22
  • $\begingroup$ What is 1 / (n - n)! ? $\endgroup$
    – gnasher729
    Jan 23, 2015 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, 2015 at 12:48

2 Answers 2

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$
2
  • $\begingroup$ @anorton Thanks for the edit. My answer was migrated from Stackoverflow where latex doesn't work. $\endgroup$ Jan 29, 2015 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, 2015 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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .