note
Elgon
[Blokhead],
<p>A query; Surely it is possible only to solve the problem in exactly O(n) when there is one more peg than discs <em>plus one</em>. (It could be that I misunderstand the O(n), O(log n), O(n^2) notation...)
<p>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.
<p>Example 2: Where there are three rings and four pegs, each ring only moves twice.
<p>[Elgon]
<p><b>UPDATE:</b>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) ???
<!-- Node text goes above. Div tags should contain sig only -->
<div class="pmsig"><div class="pmsig-37222">
<p><p><em>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.</em>
<p>Pythagoras (582 BC - 507 BC)
</div></div>
401551
401639