?

Algorithms & Data Structures

Free Version

Upgrade subject to access all content

Easy

Three Cases of the Master Theorem

ALGOR-LZQC67

The Master Theorem concerns recurrences that typically occur in divide-and-conquer algorithms. Specifically, it concerns recurrences of the form:

$$T(n) = aT\left(\frac{n}{b}\right) + f(n) \text { where } a \in [1, \infty), \text{ and } b \in (1, \infty)$$

Which THREE of the following statements comprise the three cases of the so-called Master Theorem for solving recurrences?

A

If $f(n) = O(n^c)$ where $c > \log_ba$, then $T(n) = \Theta(n^{\log_ba})$.

B

If $f(n) = O(n^c)$ where $c < \log_ba$, then $T(n) = \Theta(n^{\log_ba})$.

C

If $f(n) = \Theta(n^c\log^kn)$ where $c < \log_ba$, then $T(n) = \Theta(n^c \log^{k} n)$.

D

If $f(n) = \Theta(n^c\log^kn)$ where $c = \log_ba$, then $T(n) = \Theta(n^c \log^{k+1} n)$.

E

If $f(n) = \Omega(n^c)$ where $c > \log_ba$, then $T(n) = \Theta(f(n))$.

F

If $f(n) = \Omega(n^c)$ where $c > \log_ba$, and $af(n/b) \leq kf(n)$ for some constant $k$ and $n$ sufficiently large, then $T(n) = \Theta(f(n))$.