Use master theorem to calculate time complexity for the given recurrence relation.

Shivam @shivampatidar
17 Aug 2017 05:50 pm



Shivam @shivampatidar
17 Aug 2017 05:51 pm


set2018 @setgate
17 Aug 2017 06:29 pm

pls explain full method

venkat @saikumartadi
17 Aug 2017 08:01 pm

T(n) = T(n/2) + n(2−cosn) =⇒ Does not apply. We are in Case 3, but the regularity condition is violated. (Consider n = 2πk, where k is odd and arbitrarily large. For any such choice of n, you can show that c ≥ 3/2, thereby violating the regularity condition.)

i would recommend to read masters theorem by concept from coremen or watch the videos of oresoft in youtube most of us just biheart that formulaes but they cover 70 percent of the cases so brother watch those videos in youtube they r good and deal with exceptional cases as well even if i explain u the answer u wont understand it here and i also dont remember :p