Recurrence equation: $T(n) = 2T(n − 1) + (\log n)T([\log n]) + 1$

Question

I have this recurrence equation: $T(n) = 2T(n − 1) + (\log n)T([\log n]) + 1$ that I can't approach with the Master theorem. I have no clue what to plug in and I doubt that induction would work. Any ideas?

Answer 1

Let's change the equation slightly to

$$T(n) = 2 T(n-1) + \lfloor \log_2 n\rfloor T( \lfloor \log_2 n\rfloor).$$

Then, as you crawl down from $n$ to $n/2,$ you get $T(n)\sim 2^{n/2} T(n/2) + 2^{n/2}\lfloor \log_2 n \rfloor T(\lfloor \log_2 n\rfloor)=2^{n/2} \left(T(n/2) +\lfloor \log_2 n \rfloor T(\lfloor \log_2 n\rfloor) \right) $ On the next step, the $\log_2 n$ decreases by $1.$ So the final asymptotic will be something like $T(n) \sim n 2^n$