# algorithm analysis – Towers of Hanoi with sufficiently many stacks, show that \$T_k(n)=Theta(n)\$ for all \$kgeq 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 $$kgeq 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)approxTheta(2cdotlfloorfrac{k}{2}rfloor)+Theta(text{boundary case})$$