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