1
$\begingroup$

I have been trying this Towers of Hanoi question since last week but never able to come with the right approach towards the solution.

The setup is the standard Towers of Hanoi, except that moving the smallest disk costs one unit of time, moving the second-smallest disk takes two units of time and so on.

What is the total minimum time solving towerOfHanoi?

$\endgroup$
2
$\begingroup$

Hint. Set up a recurrence relation similar to the one for the standard Towers of Hanoi. Then use the techniques from our reference question on recurrence relations to solve the recurrence.

$\endgroup$
2
$\begingroup$

Starting from this system:

$$ \begin{cases} T(1) = 1 \\ T(n) = 2T(n-1) + n \end{cases} $$

To use repertoire method to solve the system, we'll generalize it as this:

$$ \begin{cases} T(1) = \alpha \\ T(n) = 2T(n-1) + \beta n + \gamma \end{cases} \tag 0 $$

The result must look like this:

$$ T(n) = A(n) \alpha + B(n) \beta + C(n) \gamma $$

I. Let's try T(n) = 1 $$ \begin{cases} T(1) = 1 = \alpha \\ T(n) = 1 = 2T(n-1) + \beta n + \gamma = 2 \cdot 1 + \beta n + \gamma \end{cases}$$ Thus: $$ (\alpha, \beta, \gamma) = (1, 0, -1) $$ Which means that $$ T(n) = A(n) - C(n) = 1 \tag 1 $$.

II. Now try T(n) = n $$ \begin{cases} T(1) = 1 = \alpha \\ T(n) = n = 2T(n-1) + \beta n + \gamma = 2n - 2 + \beta n + \gamma \end{cases}$$ Thus: $$ (\alpha, \beta, \gamma) = (1, -1, 2) $$ Which means that $$ T(n) = A(n) - B(n) + 2 C(n) = n \tag 2 $$.

III. Also, for $ (\alpha, \beta, \gamma) = (1, 0, 0) $: $$\begin{cases} T(1) = 1 \\ T(n) = 2T(n-1) = 2^n \end{cases}$$ Which means that $$ T(n) = A(n) = 2^{n-1} \tag 3$$.

From (1) and (3): $$ 2^{n-1} - 1 = C(n) $$

Now from this equation and (2): $$2^{n-1} - B(n) + 2 (2^{n-1} -1) = n$$ $$2^{n-1} - n + 2^n -2 = B(n) $$

Final result for $ (\alpha, \beta, \gamma) = (1, 1, 0) $: $$ T(n) = A(n) + B(n) $$ $$ T(n) = 2^{n-1} + 2^{n-1} - n + 2^n -2 $$ $$ T(n) = 2^{n+1} - n - 2$$

$\endgroup$

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.