Recurrence Relation


Q21.

The solution to the recurrence equation T(2^{k})=3T(2^{k-1})+1,T(1)=1 is
GateOverflow

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?
GateOverflow

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 is
GateOverflow

Q24.

The recurrence equation T(1) = 1 T(n) = 2T(n - 1) + n, n \geq 2 evaluates to
GateOverflow

Q25.

The recurrence relation that arises in relation with the complexity of binary search is:
GateOverflow

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
GateOverflow