If we use a recursion tree for solving $$\begin{cases} T(*,1)=T(1,*)=a \\ T(n,k)=T(n/2,k)+T(n,k/4)+kn \end{cases}$$
What is the height of the recursion tree?
Any idea or solution highly appreciated.
If we use a recursion tree for solving $$\begin{cases} T(*,1)=T(1,*)=a \\ T(n,k)=T(n/2,k)+T(n,k/4)+kn \end{cases}$$
What is the height of the recursion tree?
Any idea or solution highly appreciated.
For every $(i,j)$, consider $$t(i,j)=2^{-i}4^{-j}T(2^i,4^j),$$ then $t(i,0)=t(0,j)=a$ for every nonnegative $(i,j)$ and, for every positive $(i,j)$, $$t(i,j)=\tfrac12t(i-1,j)+\tfrac14t(i,j-1)+1.$$
Let $\ell\geqslant1$. If $t(i,j)\leqslant C$ for every $(i,j)$ such that $i+j=\ell-1$, then, for every $(i,j)$ such that $i+j=\ell$, $t(i,j)\leqslant\frac12C+\frac14C+1$, that is, $t(i,j)\leqslant C$ under the condition that $C\geqslant\max\{4,a\}$.
Assume that $a\gt0$. The computation above proves that $T(2^i,4^j)\leqslant C2^i4^j$ for every positive positive $(i,j)$ and for some $C$ large enough depending on $a$. On the other hand, every $T(n,k)$ is positive hence $T(n,k)\geqslant nk$ for every $n\geqslant2$ and $k\geqslant2$. To sum up, on the range $n\geqslant2$ and $k\geqslant2$, $$T(n,k)=\Theta(nk).$$ This approach works for every recursion $$T(n,k)=T(\alpha n,k)+T(n,\beta k)+\gamma nk,$$ provided $(T(1,k))$ and $(T(n,1))$ are bounded and $$\alpha+\beta\lt1.$$