1. Computer Science Engineering (CSE)
  2. Design and Analysis of Algorithms
  3. 7 T (n/2) + 1/n
Q.

7 T (n/2) + 1/n

A. t(n) = o(n)
B. t(n) = o(log n)
C. t(n) = o(n2log n)
D. cannot be solved using master’s theorem
Answer» D. cannot be solved using master’s theorem
Explanation: 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.

Discussion