# Recurrence Relation Algorithm Mock Test – 1

 Question 1
Select the correct asymptotic complexity of an algorithm with runtime $T(n, n)$ where

$T(x, c) = \Theta (x) \;\;\;\text{ for } c \leq 2,$
$T(c, y) = \Theta (y) \;\;\;\text{ for } c \leq 2,$ and
$T(x, y) = \Theta (x + y) + T(x/2, y/2).$
 A $\Theta (\log n)$ B $\Theta (n)$ C $\Theta (n \log n)$ D $\Theta (n^2)$
Algorithm
Question 1 Explanation:
The correct answer is $\Theta (n)$. To see why, we rewrite the recurrence relation to avoid $\Theta$ notation as follows:
$T(x, y) = c (x + y) + T(x/2, y/2).$
We may then begin to replace $T(x/2, y/2)$ with the recursive formula containing it:
$T(x, y) = c (x + y) + c\left ( \frac{x+y}{2} \right )+c\left ( \frac{x+y}{4} \right )+c\left ( \frac{x+y}{8} \right )+...$
This geometric sequence is bounded from above by $2c(x + y)$, and is obviously bounded from below by $c(x + y)$. Therefore, $T(x, y)$ is $\Theta (x+y)$, and so $T(n, n)$ is $\Theta (n)$.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 2
Select the correct asymptotic complexity of an algorithm with runtime $T(n, n)$ where

$T(x, c) = \Theta (x) \;\;\;\text{ for } c \leq 2,$
$T(x, y) = \Theta (x) + S(x,y/2),$
$S(c, y) = \Theta (y) \;\;\;\text{ for } c \leq 2, \text{ and}$
$S(x, y) = \Theta (y) + T(x/2, y).$
 A $\Theta (\log n)$ B $\Theta (n)$ C $\Theta (n \log n)$ D $\Theta (n^2)$
Algorithm
Question 2 Explanation:
The correct answer here is $\Theta (n)$. To see why, we want to first eliminate the mutually recursive recurrence relations. To do so, we will replace all references to the function $S(x, y)$ with the definition of $S(x, y)$. This yields the following recurrence relation for $T(x, y)$:

$T(x, y) = \Theta (x) + \Theta (y/2) +T(x/2,y/2),$

We can rewrite this to eliminate the constants and get the recurrence $T(x, y) = \Theta (x+y) + T(x/2,y/2)$. This is precisely the same recurrence relation as seen in above question, so it must have the same complexity $\Theta (n)$.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 3
Select the correct asymptotic complexity of an algorithm with runtime $T(n, n)$ where

$T(x, c) = \Theta (x) \;\;\;\text{ for } c \leq 2,$
$T(c, y) = \Theta (y) \;\;\;\text{ for } c \leq 2,$ and
$T(x, y) = \Theta (x) + T(x, y/2).$
 A $\Theta (\log n)$ B $\Theta (n)$ C $\Theta (n \log n)$ D $\Theta (n^2)$
Algorithm
Question 3 Explanation:
The correct answer is $\Theta (n \log n)$. To see why, we rewrite the recurrence relation to avoid $\Theta$ notation as follows:

$T(x, y) = c x + T(x, y/2).$
We may then begin to replace $T(x, y/2)$ with the recursive formula containing it:
$T(x,y)=\underset{\Theta (\log y) \; times}{{\underbrace{cx+cx+cx+...+cx}}}$
As a result, $T(x, y)$ is $\Theta (x \log y)$. When we substitute n for x and y, we get that $T(n,n)$ is $\Theta (n \log n)$.

Click to Join Our Telegram Group for Latest Update of MOCK TEST

 Question 4
Consider the following recurrence:
$T(n) =2T(n/2) + \frac{n^2}{\log ^2 n}$
Which one of the following is true?
 A $T(n)=\Theta (\frac{n^2}{\log ^2 n})$ B $T(n)=\Theta (n^2)$ C $T(n)=\Theta (n \log n)$ D $T(n)=\Theta (n^2 \log n)$
Algorithm
Question 4 Explanation:
 Question 5
Consider the following recurrence:
$T(n) =2T(n/2) + \frac{n}{\log n}$
Which one of the following is true?
 A $T(n)=\Theta (\frac{n^2}{\log n})$ B $T(n)=\Theta (n^2)$ C $T(n)=\Theta (n \log n)$ D $T(n)=\Theta (n \log \log n)$
Algorithm
Question 5 Explanation:
Using extended master theorem,
$T (n) = \Theta ( n \log \log n)$