$T(n) = 2T(n/2) +\lg(n!) $ asymptotic bounds $T(n) = 2T(n/2) + \lg(n!)$
What are the upper and lower bounds of this equation?
 A: 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.
A: $$\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}$$
