Solve the recurrence relation: T(n) = 3 T(n/2) + n^1.5 log n

+2 votes

Solve the recurrence relation: T(n) = 3 T(n/2) + n1.5 log n

asked Dec 14, 2016 in Divide & Conquer by Amrinder Arora (206 points)

1 Answer

+1 vote
 
Best answer

a = 3 > 2^1.5

T(n) = θ(n^log23)

answered Feb 15 by liyanbo Active (312 points)
selected Feb 15 by Amrinder Arora
I don't quite understand why we could get rid of the logn to use master theory to compare log23 with 1.5 .
We now that log n = o(n^0.001)  (or any small epsilon).  // small oh

Therefore, n^1.5 log n = o (n^1.50001) = o(n^log2(3))   // small oh

And therefore, the Master Theorem allows us to conclude T(n) = θ(n^log2(3))
THX professor.
The Book: Analysis and Design of Algorithms | Presentations on Slideshare | Lecture Notes, etc
...