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.

Elgon

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) ???