Question

Question about algorithm complexity: "Prove that the recursive solution to the towers of Hanoi problem is optimal. That is, show that any solution requires at least (2^N) - 1 moves."
I will add my answer and my question on my second post.

Answer 1

An algorithm that takes 2^n - 1 moves will have recurrence formula of the form:
\[Tn = 2*T(n-1) + 1\] for n >= 2 and \[T(1) = 1\]
It's easy to see that this solution holds inductively. Now suppose that\[Tj < Tn\] is a solution that takes less steps than Tn. Through induction, we have that:\[Tj < 2*(2*T(n-2) + 1) + 1\] More generally: \[Tj < 2^k*T(n-k) + 2*k + 1\] For k = n-1, we have: \[Tj < 2^(n-1) + 2*(n-1) + 1\]
And I am stuck there. My question is: I am unsure whether or not I correctly assessed the problem. How should I tackle it? It seems like what I did is a very redundant argument. Any ideas? Or better ways to tackle the problem :-)

Answer 2

I don't know how to do it. But I don't think you can get there from the way you're doing it. 2^n - 1 is the number of steps for the recursive algorithm. They're saying (what you have to prove is) that no solution can take fewer moves than this. Certainly, the absolute minimum any conceivable solution could take is n, because you have to move every piece at least once. So, there might be a solution between n and 2^n - 1.

I think usually these kinds of problems are best handled with proof by contradiction. Supposed that there is an algorithm that takes fewer than 2^n - 1 moves, then find some contradiction.

Answer 3

Thanks mate, you gave me the idea to solve it. At least, I think I solved it now. I was trying to contradict in the recurrence relation, but the better way I found is to prove that \[T(n-1)\] is the least numbers of moves(proof via analysis of the problem) and then prove that \[2^N - 1\] is a solution to the recurrence relation.