Suppose a list with N-nodes is passed to reverse and reverse2. Both recursive ve
ID: 3604856 • Letter: S
Question
Suppose a list with N-nodes is passed to reverse and reverse2. Both recursive versions make a recursive call on list.next, that will be a list with N-1 nodes. If R(n) is the time for reverse to execute on an N-node list and T(n) is the time for reverse2 to execute on an N-node list. The recursive calls will correctly reverse the N-1 nodes in time R(N-1) for reverse and T(N-1) for reverse2. Write the complete recurrence for R(N) and T(N) accounting for every statement in each method. Note that R(1) is O(1) and T(1) is O(1) since both methods do a constant-time amount of work for a list with zero or one node (there's nothing to reverse). You should choose from the following and explain how the code reflects the recurrence you choose.
R(N) is the time for reverse to execute on an N-node list. Choose one
R(N) = R(N-1) + O(1)
R(N) = R(N-1) + O(N)
T(N) is the time for reverse2 to execute on an N-node list. Choose one
T(N) = T(N-1) + O(1)
T(N) = T(N-1) + O(N)
After making each choice, write down the solution to the recurrence. Use the table below to choose the solution
Recurrence
Solution
Algorithm
T(N) = T(N-1) + O(1)
O(N)
Sequential search/find min
T(N) = T(N-1) + O(N)
O(N2)
Selection sort on array
T(N) = 2T(N-1) + O(1)
O(2N)
Towers of Hanoi
T(N) = 2T(N/2) + O(N)
O(N log N)
Merge/Quick sort
T(N) = T(N/2) + O(1)
O(log N)
Binary search or search tree
T(N) = 2T(N/2) + O(1)
O(N)
Tree traversal
T(N) = T(N/2) + O(N)
O(N)
Median or Find-Kth
Recurrence
Solution
Algorithm
T(N) = T(N-1) + O(1)
O(N)
Sequential search/find min
T(N) = T(N-1) + O(N)
O(N2)
Selection sort on array
T(N) = 2T(N-1) + O(1)
O(2N)
Towers of Hanoi
T(N) = 2T(N/2) + O(N)
O(N log N)
Merge/Quick sort
T(N) = T(N/2) + O(1)
O(log N)
Binary search or search tree
T(N) = 2T(N/2) + O(1)
O(N)
Tree traversal
T(N) = T(N/2) + O(N)
O(N)
Median or Find-Kth
Explanation / Answer
R(N) is the time for reverse to execute on an N-node list. Choose one
R(N) = R(N-1) + O(1)
Since base case is conatant time and each time we make recursive call for N-1, HENCE
R(N) = R(N-1) + O(1)
T(N) is the time for reverse2 to execute on an N-node list. Choose one
T(N) = T(N-1) + O(1)
T(N) seems to be similar to R(N)
Hence the time complexity will be R(N) = O(N)
Similiatrly, the time complexity will be T(N) = O(N)
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.