DSSSB PGT 2021
November 25, 2023Operating-Systems
November 25, 2023Data-Structures
| Question 22 |
The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is
| T(n) = 2T(n – 2) + 2 | |
| T(n) = 2T(n – 1) + n | |
| T(n) = 2T(n/2) + 1 | |
| T(n) = 2T(n – 1) + 1 |
Question 22 Explanation:
The recurrence equation for given recurrence function is
T(n) = 2T(n – 1) + 1
= 2 [2T(n – 2) + 1] + 1
= 22 T(n – 2) + 3
⋮
= 2k T( n – k) + (2k – 1)
n – k = 1
= 2n-1 T(1) + (2n-1 – 1)
= 2n-1 + 2n-1 – 1
= 2n – 1
≌ O(2n)
T(n) = 2T(n – 1) + 1
= 2 [2T(n – 2) + 1] + 1
= 22 T(n – 2) + 3
⋮
= 2k T( n – k) + (2k – 1)
n – k = 1
= 2n-1 T(1) + (2n-1 – 1)
= 2n-1 + 2n-1 – 1
= 2n – 1
≌ O(2n)
Correct Answer: D
Question 22 Explanation:
The recurrence equation for given recurrence function is
T(n) = 2T(n – 1) + 1
= 2 [2T(n – 2) + 1] + 1
= 22 T(n – 2) + 3
⋮
= 2k T( n – k) + (2k – 1)
n – k = 1
= 2n-1 T(1) + (2n-1 – 1)
= 2n-1 + 2n-1 – 1
= 2n – 1
≌ O(2n)
T(n) = 2T(n – 1) + 1
= 2 [2T(n – 2) + 1] + 1
= 22 T(n – 2) + 3
⋮
= 2k T( n – k) + (2k – 1)
n – k = 1
= 2n-1 T(1) + (2n-1 – 1)
= 2n-1 + 2n-1 – 1
= 2n – 1
≌ O(2n)
Subscribe
Login
0 Comments