Tower of Hanoi (Tower of Hanoi)

From Algorithm Wiki
Revision as of 09:12, 28 April 2023 by Admin (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search


The Tower of Hanoi puzzle consists of $n$ discs, no two of the same size, stacked on $p \geq 3$ vertical pegs, in such a way that no disc lies on top of a smaller disc. A permissible $move$ is to take the top disc from one of the pegs and move it to one of the other pegs, as long as it is not placed on top of a smaller disc. Initially, they are all stacked on the first peg. The goal is to end up with them all stacked on the last peg.


$n$: number of discs

$p$: number of pegs

Table of Algorithms

Name Year Time Space Approximation Factor Model Reference
Iteration based 1883 $O({2}^n)$ $O(n)$ Exact Deterministic
Recursion based 1940 $O({2}^n)$ $O(n \log n)$ Exact Deterministic
Non-recursion based 1940 $O({2}^n)$ $O(n)$ Exact Deterministic
Gray-code based 1940 $O({2}^n)$ $O(n)$ Exact Deterministic
Hanoi graph 2008 $O({2}^n)$ Exact Deterministic Time

Time Complexity Graph

Tower of Hanoi - Time.png