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:

There are 5 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.

Question 23 logn is correct??

Asnwer O(log log n) is correct. Please check the detailed solution.