engineering recuitment UKPSC Polytechnic Lecturer Mock Test 2024 Algorithms Asymptotic Worst Case Time and Time Complexity Introduction
We solve Tower of Hanoi problem recursively breaking the task into three section, which of the following recurrence will accord well with the approach, that is, shows correct order of work done on each recursive step?
1
T (n) = T (n – 1) + 1 + T (n – 1)
2
T (n) = T (n – 1) + T (n – 1) + 1
3
T (n) = 1 + T (n – 1) + T (n – 1)
4
T(n) = T (n – 1) + T (n – 1) + 2