I do know of the master method. In fact, I ran into this problem while doing exercises in that method. The problem is that this is one of the borderline cases that do not fall into the master method. i.e. O (n ^ (log a to base b)) is not polynomially larger or smaller than f(n) which is n^2 lg n in this case.
I think I got the solution by making a recursion tree though. I have it as O (( n lg n )^2) and proved it as the asymptotic upper bound. Havent got the lower bound yet. Thanks, Ajeet On 5/25/06, Vijendra Singh <[EMAIL PROTECTED]> wrote: > this might be helpful... > > http://en.wikipedia.org/wiki/Master_theorem > > -Vijju > > > On 5/25/06, A S Grewal <[EMAIL PROTECTED]> wrote: > > > > Hi Everyone, > > > > Does anyone know how one could compute the order of the following > > recursive function : > > > > T(n) = 4 T(n/2) + n^2 (lg n) > > > > Also, how do you handle floor and ceiling functions while determining > > order? I think they can just be ignored but is there a more rigorous > > mathematical method to determine the order? > > > > > > > > > > > > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
