Tower of Hanoi complexity analysis — [Notes]

· What is Tower of Hanoi
· Time Complexity
· Explanation of 2^n
· Space Complexity
∘ N = 3
∘ Max Calls? = Depth of Recursion Tree
· Reference

What is Tower of Hanoi

Time Complexity

If there are certain number of recursive calls and those recursive calls ends up doing constant time operation in the base case for those calls the complexity is (BranchingFactor)^n

For tower of Hanoi, Branching factor is 2

• two recursive calls inside main function
• base case is printing the string

Explanation of 2^n

Space Complexity

• Not storing disc only printing them → O(1) space
• Call stack cost?

N = 3

Max Calls? = Depth of Recursion Tree

Max calls on stack = 3 = Depth of Recursion Tree

Maximum number of entries that can be created is max N

i.e. cannot have no more than N can be recursion tree depth

Reference

Recurrence Relation for the Towers of Hanoi