Right way to solve this reccurence relation?

Question

I am not that good in mathematics , I have solved many simple relations. But I am not be able to solve the following. This is not a homework. I found it during analysis of a program.

$T(n)=2T(n-1)+\log(2T(n-1))$

Answer 1

An exact solution is very unlikely. However, if you disregard the $\log$ term, you see that $T(n) \approx 2^n \cdot T_0$. If you substitute this into the logarithmic term, you get something of the sort:

$$ T(n) = 2 T(n - 1) + n + 1 + \log T_0 $$

You can solve this to get a better approximation, and perhaps get asymptotics or bounds on $T(n)$.

Answer 2

Since $T_n \approx 2^nT_0$, let $T_n = 2^nT_0u_n $.

Then

$\begin{array}\\ T(n) &= 2T(n-1)+\log(2T(n-1))\\ \text{so}\\ 2^nT_0u_n &= 2\cdot 2^{n-1}T_0u_{n-1}+\log(2\cdot 2^{n-1}T_0u_{n-1})\\ \text{or}\\ u_n &= u_{n-1}+\dfrac{n\log(2)+\log(T_0)}{2^nT_0}+\dfrac{\log(u_n)}{2^nT_0}\\ \end{array} $

From this you can show that $\lim_{n \to \infty} u_n$ exists, so $T_N \approx c2^n$ where $c = \lim_{n \to \infty} u_n $.