Recursion based (Tower of Hanoi Tower of Hanoi)

Time Complexity

$O({2}^n)$

Space Complexity

$O(n \log n)$ bits

(Need to keep track of an O(n)-sized recursive stack, each entry requiring O(log n) space (i.e. which tower size to manipulate))

Approximate?

Exact

Randomized?

No, deterministic

Model of Computation

Word RAM

Year

1940

Reference

NA