Recurrence Relation
Q1.
For constants a\geq 1 and b \gt 1, consider the following recurrence defined on the non-negative integers: T(n) = a \cdot T \left(\dfrac{n}{b} \right) + f(n) Which one of the following options is correct about the recurrence T(n)?Q2.
For parameters a and b, both of which are \omega(1) , T(n)=T(n^{1/a})+1, and T(b)=1. Then T(n) isQ3.
The running time of an algorithm is given by:T(n)=\left\{\begin{matrix} T(n-1)+T(n-2)-T(n-3), &\text { if } n>3\\ n, &\text{ otherwise}\end{matrix}\right.Then what should be the relation between T(1),T(2),T(3), so that the order of the algorithm is constant?Q4.
Which one of the following correctly determines the solution of the recurrence relation with T(1) = 1? T(n)=2T(\frac{n}{2})+lognQ5.
Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre-specified pair of integers i,j with i \lt j. Given a shortcut i, j if you are at position i on the number line, you may directly move to j. Suppose T(k) denotes the smallest number of steps needed to move from k to 100. suppose further that there is at most 1 shortcut involving any number, and in particular from 9 there is a shortcut to 15. Let y and z be such that T(9) = 1 + min(T(y), T(z)). Then the value of the product yz is_______.Q6.
Consider the following recurrence relation. T\left ( n \right )=\left\{\begin{array} {lcl} T(n/2)+T(2n/5)+7n & \text{if} \; n > 0\\1 & \text{if}\; n=0 \end{array}\right. Which one of the following options is correct?Q7.
Consider the following recurrence:T(n)=2T\left ( \sqrt{n}\right )+1, T(1)=1Which one of the following is true?Q9.
Consider the recurrence function T(n)=\left\{\begin{matrix} 2T(\sqrt{n})+1, & n \gt 2\\ 2,& 0 \lt n\leq 2 \end{matrix}\right. Then T(n) in terms of \theta notation isQ10.
The recurrence relation that arises in relation with the complexity of binary search is: