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


There are 5 questions to complete.

10 thoughts on “Recurrence Relation”

  2. Question 24 of Recurrence relation
    opt B – (3^(k+1) – 1) / 2
    please remove the extra -1 that is there in the option.

    Reply

Leave a Comment