Question

The time complexity of the solution tower of hanoi problem using recursion is _________

(a) O(n^2)

(b) O(2^n)

(c) O(n log n)

(d) O(n)

I got this question at a job interview.

The above asked question is from Recursion in division Recursion of Data Structures & Algorithms II

Answer 1

The correct answer is (b) O(2^n)

The explanation is: Time complexity of the problem can be found out by solving the recurrence relation: T(n)=2T(n-1)+c. Result of this relation is found to be equal to 2^n. It can be solved using substitution.