Algorithm
Q163.
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?Q164.
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 isQ166.
The recurrence relation that arises in relation with the complexity of binary search is:Q167.
The running time of the following algorithm Procedure A(n) If n \leq 2 return (1) else return (A(\sqrt{n})); is best discribed byQ168.
Consider the following array.\begin{array}{|l|l|l|l|l|l|l|l|} \hline 23&32&45&69&72&73&89&97 \\ \hline\end{array} Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order?Q169.
Of the following sort algorithms, which has execution time that is least dependant on initial ordering of the input?Q170.
An array of 25 distinct elements is to be sorted using quicksort. Assume that the pivot element is chosen uniformly at random. The probability that the pivot element gets placed in the worst possible location in the first round of partitioning (rounded off to 2 decimal places) is _________.