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.