Question 1 |

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

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

if f(n) is n \log_2(n), then T(n) is \Theta(n \log_2(n)). | |

if f(n) is \dfrac{n}{\log_2(n)}, then T(n) is \Theta(\log_2(n)). | |

if f(n) is O(n^{\log_b(a)-\epsilon}) for some \epsilon \gt 0, then T(n) is \Theta(n ^{\log_b(a)}). | |

if f(n) is \Theta(n ^{\log_b(a)}), then T(n) is \Theta(n ^{\log_b(a)}). |

Question 1 Explanation:

Question 2 |

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?

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?

T(n)=\Theta (n^{5/2}) | |

T(n)=\Theta (n \log n) | |

T(n)=\Theta (n) | |

T(n)=\Theta ((\log n)^{5/2}) |

Question 2 Explanation:

Question 3 |

The master theorem

assumes the subproblems are unequal sizes | |

can be used if the subproblems are of equal size | |

cannot be used for divide and conquer algorithms | |

cannot be used for asymptotic complexity analysis |

Question 3 Explanation:

Question 4 |

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

\Theta (\log _a \log_b n) | |

\Theta (\log _{ab} n) | |

\Theta (\log _b \log_a n) | |

\Theta (\log _2 \log_2 n) |

Question 4 Explanation:

Question 5 |

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?

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?

T(1) = T(2) = T(3) | |

T(1) + T(3) = 2T(2) | |

T(1) - T(3) = T(2) | |

T(1) + T(2) = T(3) |

Question 5 Explanation:

Question 6 |

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

T(n)=2 T\left(\frac{n}{2}\right)+k, \mathrm{k} \text { is a constant } | |

T(n)=T\left(\frac{n}{2}\right)+k, \mathrm{k} \text { is a constant } | |

T(n)=T\left(\frac{n}{2}\right)+\log n | |

T(n)=T\left(\frac{n}{2}\right)+n |

Question 6 Explanation:

Question 7 |

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 is

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 is

\theta (log log n) | |

\theta (logn) | |

\theta (\sqrt{n}) | |

\theta (n) |

Question 7 Explanation:

Question 8 |

Consider the following recurrence:

T(n)=2T\left ( \sqrt{n}\right )+1, T(1)=1

Which one of the following is true?

T(n)=2T\left ( \sqrt{n}\right )+1, T(1)=1

Which one of the following is true?

T(n)=\Theta (\log\log n) | |

T(n)=\Theta (\log n) | |

T(n)=\Theta (\sqrt{n}) | |

T(n)=\Theta (n) |

Question 8 Explanation:

Question 9 |

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_______.

100 | |

150 | |

50 | |

200 |

Question 9 Explanation:

Question 10 |

Which one of the following correctly determines the solution of the recurrence relation with
T(1) = 1?

T(n)=2T(\frac{n}{2})+logn

T(n)=2T(\frac{n}{2})+logn

\theta (n) | |

\theta (n logn) | |

\theta (n^{2}) | |

\theta (log n) |

Question 10 Explanation:

There are 10 questions to complete.

Question 19 has typo. please correct it.

can you please specify the exact typo you have identified?

T(n)=2T(n/2)+n

in qus 19 there is no “2” multiplied

Thank You Ramananda Samantaray,

We have updated the question

Question 24 of Recurrence relation

opt B – (3^(k+1) – 1) / 2

please remove the extra -1 that is there in the option.

Thank You Ramananda Samantaray,

We have updated the option.

update question 15. No option is correct

Options are as per given in GATE paper. Correct answer is 13.