$T(n) = 2T(n/2) +\lg(n!) $ asymptotic bounds

Question

$T(n) = 2T(n/2) + \lg(n!)$

What are the upper and lower bounds of this equation?

Answer 1

This is certainly defined for powers of $2$. So set $n=2^k$ and study the sequence defined by $x_k:=T(2^k)$, like in the other question you asked today. Then $x_k$ satisfies $$ x_k=2x_{k-1}+\log(2^k!)\qquad\forall k\geq 1. $$ Now try to prove, by an easy induction, that $x_k$ is nonnegative and greater than a sequence which tends to $+\infty$. All at once.

Hint: $\log(2^k!)\geq \log (2^k)=k\log 2$.

If you can do this, you will have proved that $$ \lim_{k\rightarrow+\infty}x_k=\lim_{n\rightarrow+\infty}T(n)=+\infty. $$ A fortiori, there is no upper bound. And there are infinitely many lower bounds. $0$ is one of them.

Answer 2

$$\log(n!) \sim n\log(n)$$ Hence, we have $$T(n) \sim 2T(n/2) + n \log(n)$$ Setting $n=2^k$, and calling $T(2^k) = g(k)$, we get that \begin{align} g(k) & \sim 2g(k-1) + k2^k \log(2) \sim k 2^k \log(2) + 2((k-1)2^{k-1} \log(2) + 2g(k-2))\\ & \sim k 2^k \log(2) + (k-1)2^k \log(2) + 4 g(k-2)\\ & \sim k 2^k \log(2) + (k-1)2^k \log(2) + 4 ((k-2)2^{k-2} \log(2) + 2g(k-3))\\ & \sim k 2^k \log(2) + (k-1)2^k \log(2) + (k-2)2^{k} \log(2) + 8g(k-3)\\ & \sim k 2^k \log(2) + (k-1)2^k \log(2) + (k-2)2^{k} \log(2) + \cdots + 2^k \log(2) + 2^kg(0)\\ & \sim k(k+1) 2^{k-1} \log(2) + 2^k g(0)\\ & \sim (k+1) 2^{k-1} \log(2^k) \end{align} Hence, $$T(n) \sim \dfrac{n\log^2(n)}{2 \log 2}$$