0
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ That second recurrence only makes sense when $n$ and $k$ are multiples of $2$ and $4$ respectively. What if they aren't? $\endgroup$ Aug 21, 2014 at 20:02
  • $\begingroup$ That leaves the $k/4$ still. Could you include more context about what $T(n,k)$ is counting? $\endgroup$ Aug 21, 2014 at 20:10
  • $\begingroup$ @MounaMokhiab Show us how much you are able to do by yourself. What is the height in the $T(*, 1)$ case? What are the heights in the cases $$\begin{array} {c|c|c} T(2,4) & T(2,16) & T(2, 64) \\ \hline T(4,4) & T(4,16) & T(4, 64) \\ \hline T(8,4) & T(8,16) & T(8, 64) \end{array}$$ $\endgroup$
    – DanielV
    Aug 21, 2014 at 20:36
  • $\begingroup$ Got something from the answer below? $\endgroup$
    – Did
    Aug 25, 2014 at 11:38
  • $\begingroup$ If you are waiting for somebody to prove that $T(n,k)$ is $O(\log n+\log k)$, then, as already mentioned, you are in for a loooong wait... $\endgroup$
    – Did
    Aug 25, 2014 at 13:35

1 Answer 1

1
$\begingroup$

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.$$

$\endgroup$
8
  • $\begingroup$ Interesting. One may note that, if $a\gt0$ then every $T(n,k)\gt0$ hence, skipping most of the RHS of the recursion yields $T(n,k)\geqslant nk$ for every $(n,k)$ such that $n\geqslant2$ and $k\geqslant2$. $\endgroup$
    – Did
    Aug 21, 2014 at 21:09
  • $\begingroup$ $$T(n,k)=T(n/2,k)+T(n,k/4)+nk\implies T(n,k)\gt nk$$ $\endgroup$
    – Did
    Aug 21, 2014 at 21:11
  • $\begingroup$ To show that $T(n,k)=O(\log n+\log k)$ after I got a proof that $T(n,k)=\Theta(nk)$... I am afraid this is slightly too postmodern for me. $\endgroup$
    – Did
    Aug 21, 2014 at 21:16
  • $\begingroup$ Did you get the VERY SIMPLE argument showing that this is IMPOSSIBLE? I hope so. $\endgroup$
    – Did
    Aug 21, 2014 at 21:22
  • $\begingroup$ @EhsanM.Kermani Sure--now that they modified the question... Sorry but I am not ready to play at these games. $\endgroup$
    – Did
    Aug 21, 2014 at 23:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .