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

Click Here to Practice ALL Previous MOCK TEST FREE
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

Click Here to Practice ALL Previous MOCK TEST FREE
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

Click Here to Practice ALL Previous MOCK TEST FREE
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 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 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 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

Click Here to Practice ALL Previous MOCK TEST FREE
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

Click Here to Practice ALL Previous MOCK TEST FREE
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

Click Here to Practice ALL Previous MOCK TEST FREE
Question 10
Consider the following recurrence:
T(n)=T\left ( \frac{n}{3} \right )+T\left ( \frac{2n}{3} \right )+cn
Which one of the following is true?
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)
   Algorithm
There are 10 questions to complete.

Leave a Comment