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

Question

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

Answer 1

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