Recurrence Relation
Q22.
Consider a list of recursive algorithms and a list of recurrence relations as shown below. Each recurrence relation corresponds to exactly one algorithm and is used to derive the time complexity of the algorithm. \begin{array}{|l|l|l|l|}\hline \text{} & \textbf{Recursive Algorithm } & \text{} & \textbf{Recurrence Relation} \\\hline \text{P} & \text{Binary search} & \text{l.} & \text{$T(n) = T(n-k) +T(k) +cn$} \\\hline \text{Q.} & \text{Merge sort} &\text{ll.} & \text{$T(n) = 2T(n-1) + 1$ }\\\hline\text{R.} & \text{Quick sort}& \text{lll.} & \text{$T(n) = 2T(n/2) + cn$}\\\hline \text{S.} & \text{Tower of Hanoi} & \text{lV.} & \text{$T(n) = T(n/2) + 1$} \\\hline \end{array}Which of the following is the correct match between the algorithms and their recurrence relations?Q23.
Consider the following recurrence relation T(1)=1 T(n+1)=T(n)+\left \lfloor \sqrt{n+1} \right \rfloor for all n \geq 1 The value of T(m^{2} ) for m \geq 1 isQ25.
The recurrence relation that arises in relation with the complexity of binary search is:Q26.
The running time of the following algorithm Procedure A(n) If n \leq 2 return (1) else return (A(\sqrt{n})); is best discribed by