# Towers of Hanoi with sufficiently many stacks, show that $T_k(n)=\Theta(n)$ for all $k\geq 2 + \frac{n-1}{2}$

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 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})$$

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

• 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. – John L. Mar 8 at 23:59
• 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. – John L. Mar 9 at 0:08
• 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$. – Elliott de Launay Mar 13 at 20:01