World's most popular travel blog for travel bloggers.

# How do I find running time for the following divide and conquer problem?

, ,
Problem Detail:

Question is to find the runtime $T(n)$ of following problem by solving the recurrence.

$T(n)=16\cdot T(\frac{n}{4}) + n!$.

I went through the following theory.

If the recurrence relation is of the form $T(n)=aT(\frac{n}{b}) + \Theta(n^k(\log n)^p)$,where $a \geq 1$ , $b \gt 1$, $k \ge 0$ and $p$ is a real number, then:

1. If $a \gt b^k$, then $T(n)=\Theta(n^{\log_b a})$.

2. If $a=b^k$

1. If $p \gt -1$, then $T(n)=\Theta(n^{\log_b a}(\log n)^{p+1})$.
2. If $p=-1$ then $T(n)=\Theta((n^{\log_b a}\log \log n)$.
3. If $p \lt -1$, then $T(n)=\Theta(n^{\log_b a})$.
3. If $a \lt b^k$

1. If $p \ge 0$, then $T(n)=\Theta(n^k(\log n)^p)$.
2. If $p \lt 0$, then $T(n)=O(n^k)$.

Now I want to know how do I compare the second terms of the the equations ($n!$ and $\Theta(n^k(\log n)^p)$) to obtain $k$ so that I can check which of the above case holds true ?

###### Answered By : Yuval Filmus

You cannot use the Master Theorem to solve this recurrence, since $n!$ doesn't grow like $n^c$ for any $c$. Instead, Stirling's approximation shows that $n! \sim \sqrt{2\pi n} (n/e)^n$. Rather, expand the recurrence to get $$T(n) = n! + 16 (n/4)! + 16^2 (n/16)! + \cdots.$$ Stirling's approximation shows that the latter terms are tiny compared to the first one. Therefore $$T(n) \sim n!.$$ This is just shorthand for $$\lim_{n \to \infty} \frac{T(n)}{n!} = 1.$$

If you want to prove this formally, one way is as follows. Start with the observation that $n/16 \geq 4$, $$16 (n/4)! \leq (n/4+1)(n/4)! = (n/4+1)! \leq \frac{1}{n} n!.$$ The first inequality uses $n \geq 60$, and the second $n \geq 4$. Continuing in this vain, for $n/16^2 \geq 4$, $$16^2 (n/16)! \leq \frac{1}{n/4} (n/4)! \leq \frac{1}{n/4} \frac{1}{n} n! \leq \frac{1}{n} n!.$$ In the same way we show that $16^k (n/4^k) \leq n!/n$ for $n/4^k \geq 4$. Therefore $$T(n) = n! + 16(n/4)! + 16^2(n/4^2)! + \cdots \leq n! + n!/n + n!/n + \cdots + 16^r T(4),$$ where $n/4^r = 4$, and so $r = \log_4 n - 1$, which implies $16^r = n^2/16$. Since there are $r-1 = \log_4 n - 2$ summands of the form $n!/n$, we certainly have $$T(n) \leq n! + \frac{\log_4 n}{n} n! + \frac{T(4)}{16} n^2.$$ This shows that $T(n) = n! + f(n)$, where $$f(n) = \frac{\log_4 n}{n} n! + \frac{T(4)}{16} n^2$$ is a function satisfying $$\lim_{n \to \infty} \frac{f(n)}{n!} = 0.$$ On the other hand, clearly $T(n) \geq n!$. This implies what we claimed above, $T(n) \sim n!$.