I got this recurrence to solve: $T(n) = 2.1 T(n/2) + n$.
I know the answer (got it using the plug and chug method and using the master method too), but I'm trying to solve using recurrence tree and the result doesn't match.
The problem that I'm having is how to deal with this $a$ that multiplies $T(2/n$). Anybody can give me a clue how to solve this?
HINT: $$\frac{T(n)}n=\frac{T(\frac n2)}{\frac n2}+1$$
Put $\frac{T(n)}n=F(n), F(n)=F(\frac n2)+1$
If $n=2^m, F(2^m)=F(2^r)+m-r=F(2^0)+m$