Solving recurrence relations with tightest asymptotic bounds possible

Question

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

1. T(n) = n( T(n/2)^2 )

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

3. T(n) = log(n)T(n/2) + 1

Answer 1

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)!)

Answer 2

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.