Solving recurrence relations with tightest asymptotic bounds possible We're currently covering recurrence relations in my course. I get it for the most part, but these 3 problems are throwing me off. Can someone please explain what's happening and how I would go about solving them? Thanks


*

*T(n) = n( T(n/2)^2 )

*T(n) = T(n-1) + 16lg(n)             **is lg(n) just log(n)?

*T(n) = log(n)T(n/2) + 1
 A: In the 3rd question- the final relation that you get is:
T(n)=1+log(n)+log(n)*log(n/2)+log(n)*log(n/2)*log(n/4)+....

let us write log(n) as p,
so, 
`T(n)=1+p+p*(p-1)+p*(p-1)*(p-2)+...`

     =1+p*{1+(p-1)*[1+(p-2)[1+...]]}

this can be approximated as
     =p*(p-1)*(p-2)...

which is equal to
     =p!

   so, T(n)=log(n)!

   T(n)=O(log(n)!)

A: I found Tanuj Yadav's answer to be interesting.  Here's another way of solving it:
We have:
$$T(n)=\log_2{(n)}T(n/2)+1$$
I immediately sbustitute $n=2^m$, to get:
$$\begin{align}
  T(2^m) &= \log_2{(2^m)}T(2^m/2)+1 \\
  &= m T(2^{m-1}) + 1 \tag{4}
\end{align}$$
...and the above equation now seems very manageable.  We get:
$$\begin{align}
T(2^m) &= 1 + (m + m(m-1) + m(m-1)(m-2) + \dots)\\
       &= 1 + O(m!)
\end{align}$$
Substituting $m = \log_2{(n)}$, we have:
$$T(n) = O(\log_2{(n)}!)$$
which agrees with Tanuj Yadav's answer.
I note that we could have used both $m$ and $n$ to get, for (4):
$$T(n) = m T(n-1) + 1$$
This would give, for your question (1):
$$T(m) = n \left( T(m-1)^2 \right)$$
One more thing I can't resist mentioning...  If you find recurrences as fascinating as I do, or are just curious, Herbert Wilf's GeneratingFunctionology, which you can find here is a very approachable introduction to all kinds of recurrences, and yet another take on them.
