1
$\begingroup$

I'm trying to show that for the following Towers of Hanoi general algorithm that $T_k(n)=\Theta(n)$ for all $k\geq 2 + \frac{n-1}{2}$, I'm not sure how to incorporate the restriction on $k$ into my proof.

generalTH(n_disks,k_stacks)
  if n<k: 
    ### in 2n-1 moves reassemble ### 
    return
  m = n-2
  generalTH(n-m,k)
  generalTH(m,k-1)
  generalTH(n-m,k)

To solve towers of Hanoi, I know it takes the following number of moves: $$ T_k(n) = \begin{cases} 2^n-1, & k=3 \\ 2n-1, & n<k \\ 2T_k(n-m)+T_{k-1}(m), & n \geq k \end{cases} $$ Going through it - how can I show that the boundary case of $k=3$ can be within $\Theta(n)$?

Since $m = n-2$ : When I expand the recursion it seems easy to show that the first half is in $n$ - but I'm not sure how to show the boundary case will be in $n$? $$T_k(n)=2T_k(n-(n-2))+T_{k-1}(n-2)=2T_k(2)+2T_{k-1}(n-2-(n-4))+T_{k-2}(n-4)$$ $$...$$ $$T_k(n)\approx\Theta(2\cdot\lfloor\frac{k}{2}\rfloor)+\Theta(\text{boundary case})$$

$\endgroup$
0
1
$\begingroup$

If $n\lt k$, we have $T_k(n)=2n-1$. Let us focus on the remaining case, i.e, assuming $n\ge k$.

One of the recurrence relations is, $$\quad T_k(n) =6+T_{k-1}(n-2)\ \ \text{for all }n\ge k\ge\frac {n+3}2\text{ and }n\ge3, $$ where $6$ comes from $2T_k(2)$, since $T_k(2)=3$.

Applying the recurrence relation above repeatedly, we have $$\begin{align} T_k(n)&=6\cdot 1+T_{k-1}(n-2\cdot1)\\ &=6\cdot 2+T_{k-1}(n-2\cdot2)\\ &=\cdots\\ &=6\cdot (p-1)+T_{k-(p-1)}(n-2\cdot (p-1))\\ &=6\cdot p+T_{k-p}(n-2\cdot p)\\ (\text{let us apply } T_k(n)=2n-1)\quad&=6\cdot p+2(n-2\cdot p)-1\\ \end{align}$$ if we can choose $p$ such that

  • $n-2(p-1)\ge k-(p-1)\ge\dfrac{n-2(p-1)+3}2$,
    which ensures all equalities except the last one hold, and
  • $n-2p<k-p$,
    which ensures the last equality holds.

Solving $p$ for those inequalities, we find that $p= n-k+1$.

$$T_k(n)=6\cdot p+2(n-2\cdot p)-1=4n-2k+1$$


So, we have $$T_k(n) =\begin{cases} 2n-1, & n<k \\ 4n-2k+1, & n \geq k \end{cases}$$ It is easy to check that $n\le T_k(n)<4n$, so $T_k(n)=\Theta(n)$.


"How can I show that the boundary case of $k=3$ can be within $\Theta(n)$?"

What is the situation when $k=3$ under the assumption $k\ge\dfrac{n+3}2$? That means $n\le3$. So that situation is rather irrelevant since we are interested in the asymptotic behavior of $T_k(n)$.

$\endgroup$
3
  • 1
    $\begingroup$ This answer shows the mechanic way to find and compute the answer. A much simpler understanding is to prove the final formula for $T_k(n)$ directly by induction. If $n<k$, done. Otherwise, each extra 2 disks cause 6 more steps. $\endgroup$ – John L. Mar 8 at 23:59
  • 1
    $\begingroup$ The choice of $p= n-k+1$ is, in fact, obvious. Initially, there is a difference of $n-k$ between $n$ and $k$. Each call to generalTH(n - 2, k - 1) reduce the difference by $1$. So exactly after $n-k+1$ calls, the difference becomes smaller than 0, at which time the base case of the algorithm is reached. $\endgroup$ – John L. Mar 9 at 0:08
  • $\begingroup$ Thanks - in terms of summarizing the process of applying $p$, the goal is to determine the value of the recurrence where p causes $n<k$. $\endgroup$ – Elliott de Launay Mar 13 at 20:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.