# 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)$

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

 Question 6
Consider the following recurrence:
$T(n) =2T(n/2) + \frac{n}{\log ^8 n}$
Which one of the following is true?
 A $T(n)=\Theta (\frac{n^2}{\log ^9 n})$ B $T(n)=\Theta (n)$ C $T(n)=\Theta (n \log n)$ D $T(n)=\Theta (n \log \log n)$
Algorithm
Question 6 Explanation:
 Question 7
Consider the following recurrence:
$T (n) = 16T (n/4) + n!$
Which one of the following is true?
 A $T(n)=\Theta (n^2)$ B $T(n)=\Theta (n)$ C $T(n)=\Theta (n^n)$ D $T(n)=\Theta (n^2)$
Algorithm
Question 7 Explanation:
$n!=O(n^n)$
Case -3 of master theorem can be applied.
$T (n) = \Theta (n^n)$

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

 Question 8
Consider the following recurrence:
$T(n) = \sqrt{2}T(n/2) + log n$
Which one of the following is true?
 A $T(n)=\Theta (n \log \log n)$ B $T (n) = \Theta ( \sqrt{n})$ C $T(n)=\Theta (n \log n)$ D $T (n) = \Theta ( \sqrt{n} \log n)$
Algorithm
Question 8 Explanation:
Case -1 of master theorem can be applied.
$T (n) = \Theta ( \sqrt{n})$

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

 Question 9
Consider the following recurrence:
$T (n) = 16T (n/4) + \log(n!)$
Which one of the following is true?
 A $T(n)=\Theta (n \log n)$ B $T(n)=\Theta (n^n)$ C $T(n)=\Theta (n^2)$ D $T(n)=\Theta (n^2 \log ^2 n)$
Algorithm
Question 9 Explanation:
log(n!) = log(n) + log(n-1) + ... log(2) + log(1)
Which is less than:
log(n) + log(n) + log(n) + log(n) + ... + log(n) = n*log(n)
So O(log(n!)) is a subset of O(n log(n))
So reurrence relation become
$T (n) = 16T (n/4) + O(n \log n)$
Case -1 of master theorem can be applied.
$T (n) = \Theta ( n^2)$

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

$T(n)=T\left ( \frac{n}{3} \right )+T\left ( \frac{2n}{3} \right )+cn$
 A $T(n)=\Theta (n^2)$ B $T(n)=\Theta (n \log n)$ C $T(n)=\Theta (n)$ D $T(n)=\Theta (n^2 \log n)$