Solving a recursive equations with the tree method

26 Views Asked by At

I have the following recursion formula: $$T(n)=T\left(\frac{n}{2}\right)+aT\left(\frac{n}{4}\right)+n^{2}$$ where $a\in\mathbb{Z}$ and $T(n)=1$ for $n<10$. In the solutions is suggested to use the tree method to calculate that on the left path we get $n^{2}\sum_{i=0}^{log_{4}n}(\frac{1}{4}+\frac{a}{16})$ and on the right path we get $n^{2}\sum_{i=0}^{log_{2}n}(\frac{1}{4}+\frac{a}{16})$. I don't understand why and will be glad to get an explanation. Also, Is it true to say that for: $$T(n)=T\left(\frac{n}{k}\right)+aT\left(\frac{n}{m}\right)+n^{2}$$ where $k,m\in\mathbb{N}$ we get on the left path we get $n^{2}\sum_{i=0}^{log_{m}n}(\frac{1}{4}+\frac{a}{16})$ and on the right path we get $n^{2}\sum_{i=0}^{log_{k}n}(\frac{1}{4}+\frac{a}{16})$?