ISRO2020-21

Question

The master theorem

• A. assumes the subproblems are unequal sizes
• B. can be used if the subproblems are of equal size
• C. cannot be used for divide and conquer algorithms
• D. cannot be used for asymptotic complexity analysis

Answer 1

$\underline{\textbf{Answer:}\Rightarrow}\;\mathbf{b.}$

It divides the subproblem into each of size $\mathbf{\dfrac{n}{b}}$.

Comments

Answer might be B as master theorm never give upper bound it gives tightest bound

---

Yes right, so this was also a negative for me. :(

---

Why not (D) ?

Answer 2

Answer will be (b) because

According to master's theorem we can only find the time complexity if the recurrence relation is of form

$T(n) = a\times T \left( \frac{n}{b} \right) +n^k *log^p n$

it assumes the subproblems to be of size $\left( \frac{n}{b} \right)$