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

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

\Theta (\log n) | |

\Theta (n) | |

\Theta (n \log n) | |

\Theta (n^2) |

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

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

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

\Theta (\log n) | |

\Theta (n) | |

\Theta (n \log n) | |

\Theta (n^2) |

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

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

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

\Theta (\log n) | |

\Theta (n) | |

\Theta (n \log n) | |

\Theta (n^2) |

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

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?

T(n) =2T(n/2) + \frac{n^2}{\log ^2 n}

Which one of the following is true?

T(n)=\Theta (\frac{n^2}{\log ^2 n}) | |

T(n)=\Theta (n^2) | |

T(n)=\Theta (n \log n) | |

T(n)=\Theta (n^2 \log n) |

Question 4 Explanation:

Using extended master theorem,

T (n) = \Theta ( n^2)

Refer the Extended Master Theorem

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

Click Here to Practice ALL Previous MOCK TEST FREE

T (n) = \Theta ( n^2)

Refer the Extended Master Theorem

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

Click Here to Practice ALL Previous MOCK TEST FREE

Question 5 |

Consider the following recurrence:

T(n) =2T(n/2) + \frac{n}{\log n}

Which one of the following is true?

T(n) =2T(n/2) + \frac{n}{\log n}

Which one of the following is true?

T(n)=\Theta (\frac{n^2}{\log n}) | |

T(n)=\Theta (n^2) | |

T(n)=\Theta (n \log n) | |

T(n)=\Theta (n \log \log n) |

Question 5 Explanation:

Using extended master theorem,

T (n) = \Theta ( n \log \log n)

Read the Extended Master Theorem

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

Click Here to Practice ALL Previous MOCK TEST FREE

T (n) = \Theta ( n \log \log n)

Read the Extended Master Theorem

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

Click Here to Practice ALL Previous MOCK TEST FREE

Question 6 |

Consider the following recurrence:

T(n) =2T(n/2) + \frac{n}{\log ^8 n}

Which one of the following is true?

T(n) =2T(n/2) + \frac{n}{\log ^8 n}

Which one of the following is true?

T(n)=\Theta (\frac{n^2}{\log ^9 n}) | |

T(n)=\Theta (n) | |

T(n)=\Theta (n \log n) | |

T(n)=\Theta (n \log \log n) |

Question 6 Explanation:

Using extended master theorem,

T (n) = \Theta (n)

Read the Extended Master Theorem

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

Click Here to Practice ALL Previous MOCK TEST FREE

T (n) = \Theta (n)

Read the Extended Master Theorem

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

Click Here to Practice ALL Previous MOCK TEST FREE

Question 7 |

Consider the following recurrence:

T (n) = 16T (n/4) + n!

Which one of the following is true?

T (n) = 16T (n/4) + n!

Which one of the following is true?

T(n)=\Theta (n^2) | |

T(n)=\Theta (n) | |

T(n)=\Theta (n^n) | |

T(n)=\Theta (n^2) |

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

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?

T(n) = \sqrt{2}T(n/2) + log n

Which one of the following is true?

T(n)=\Theta (n \log \log n) | |

T (n) = \Theta ( \sqrt{n}) | |

T(n)=\Theta (n \log n) | |

T (n) = \Theta ( \sqrt{n} \log n) |

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

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?

T (n) = 16T (n/4) + \log(n!)

Which one of the following is true?

T(n)=\Theta (n \log n) | |

T(n)=\Theta (n^n) | |

T(n)=\Theta (n^2) | |

T(n)=\Theta (n^2 \log ^2 n) |

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

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?

T(n)=T\left ( \frac{n}{3} \right )+T\left ( \frac{2n}{3} \right )+cn

Which one of the following is true?

T(n)=\Theta (n^2) | |

T(n)=\Theta (n \log n) | |

T(n)=\Theta (n) | |

T(n)=\Theta (n^2 \log n) |

There are 10 questions to complete.