Design and Analysis of Algorithms MCQs | Page - 4

 in third case of master’s theorem the necessary condition is that c > logba. if this condition is true then t(n) = o(f(n)).

 no we cannot solve all the recurrences by only using master’s theorem. we can solve only those which fall under the three cases prescribed in the theorem.

 the recurrence relation of merge sort is given by t(n) = 2t(n/2) + o(n). so we can observe that c = logba so it will fall under case 2 of master’s theorem.

 the recurrence relation of stooge sort is given as t(n) = 3t(2/3n) + o(1). it is found too be equal to o(n2.7) using master’s theorem first case.

 the second case of master’s theorem can be extended for a case where f(n)

 in the extended second case of master’s theorem the necessary condition is that c = logba. if this condition is true then t(n)= o(nc(log n))k+1.

 the recurrence relation of binary search is given by t(n) = t(n/2) + o(1). so we can observe that c = logba so it will fall under case 2 of master’s theorem.

 the given recurrence cannot be solved by using the master’s theorem. it is because in this recurrence relation a < 1 so master’s theorem cannot be applied.

 kmp algorithm is an efficient pattern searching algorithm. it has a time complexity of o(m) where m is the length of text.

 z algorithm is an efficient pattern searching algorithm as it searches the pattern in linear time. it has a time complexity of o(m + n) where m is the length of text and n is the length of the pattern.