in reply to Re: Hanoi Challenge

in thread Hanoi Challenge

A query; Surely it is possible only to solve the problem in exactly O(n) when there is one more peg than discs *plus one*. (It could be that I misunderstand the O(n), O(log n), O(n^2) notation...)

Example: In the quickest solution for three pegs and three discs, for example, the large disc moves once, the medium disc moves twice and the smallest disc moves four times.

Example 2: Where there are three rings and four pegs, each ring only moves twice.

**UPDATE:**Thanks to Thor for pointing out my error, below. As a general rule, I find that for n pegs and n discs the number of moves required is 2n + 1. If, however, there are n discs and n + 1 (or more) pegs, then 2n - 1 moves are required. Can someone with a better understanding of the formalisms tell me whether either of these is O(n) ???

*It is better either to be silent, or to say things of more value than silence. Sooner throw a pearl at hazard than an idle or useless word; and do not say a little in many words, but a great deal in a few.*

Pythagoras (582 BC - 507 BC)

Replies are listed 'Best First'. | |
---|---|

Re^3: Hanoi Challenge
by thor (Priest) on Oct 22, 2004 at 20:16 UTC |

Comment onRe^2: Hanoi Challenge