Question

Does the Master theorem apply to the following recurrences. Justify your answer in each case. If it applies, then also state the case and the solution. (a) T(n) = √ nT(n/2)+logn, (b) T(n) = T(n/2+ 31)+log n, (c) T(n) = T(n−1)+T(n/2)+n and (d) T(n) = T(n/7)+T(5n/13)+n.

Answer 1

The Master's Theorem is applicable only in cases where the recurrence relation is of the form T(n)=aT(n/b)+f(n) where a is greater than or equal to 1 and b is strictly greater than 1, and f is an asymptotically positive function.

(a) The Master's theorem is not applicable to this recurrence because here a=√ n which is not a constant.

(b) The Master's theorem is not applicable to this recurrence because there is no term of the form aT(n/b) in this relation.

(c) The Master's theorem is not applicable to this recurrence because the term T(n-1) does not fall in the acceptable category of terms.

(d) The Master's theorem is not applicable to this recurrence because there are two terms of the form aT(n/b) present here,