# Recurrence Relation

 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)$?
 A if $f(n)$ is $n \log_2(n)$, then $T(n)$ is $\Theta(n \log_2(n))$. B if $f(n)$ is $\dfrac{n}{\log_2(n)}$, then $T(n)$ is $\Theta(\log_2(n))$. C if $f(n)$ is $O(n^{\log_b(a)-\epsilon})$ for some $\epsilon \gt 0$, then $T(n)$ is $\Theta(n ^{\log_b(a)})$. D if $f(n)$ is $\Theta(n ^{\log_b(a)})$, then $T(n)$ is $\Theta(n ^{\log_b(a)})$.
GATE CSE 2021 SET-2   Algorithm
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?
 A $T(n)=\Theta (n^{5/2})$ B $T(n)=\Theta (n \log n)$ C $T(n)=\Theta (n)$ D $T(n)=\Theta ((\log n)^{5/2})$
GATE CSE 2021 SET-1   Algorithm
Question 2 Explanation:

 Question 3
The master theorem
 A assumes the subproblems are unequal sizes B can be used if the subproblems are of equal size C cannot be used for divide and conquer algorithms D cannot be used for asymptotic complexity analysis
ISRO CSE 2020   Algorithm
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
 A $\Theta (\log _a \log_b n)$ B $\Theta (\log _{ab} n)$ C $\Theta (\log _b \log_a n)$ D $\Theta (\log _2 \log_2 n)$
GATE CSE 2020   Algorithm
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?
 A T(1) = T(2) = T(3) B T(1) + T(3) = 2T(2) C T(1) - T(3) = T(2) D T(1) + T(2) = T(3)
ISRO CSE 2018   Algorithm
Question 5 Explanation:

There are 5 questions to complete.

### 10 thoughts on “Recurrence Relation”

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

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

3. update question 15. No option is correct

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

4. • 