I am not sure if you can use such approach for example given T(n)=2*T(n/2)+n
can be expanded also that way, but it is Omega(n log n),like merge sort T(n)=2T(n/2)+n=2(2T(n/4)+n/2 )+n=4T(n/4)+2n=4(2T(n/8)+n/4 )+2n=8T(n/8)+3n there will be always only contains linear terms, however ... 2009/4/1 Ajinkya Kale <kaleajin...@gmail.com> > The intuitive proof maybe that if you try to expand the > recursion over a few steps such that it tends to go towards T(1) > then you never see a term greater(in order) than O(n^2) .. > > > On Wed, Apr 1, 2009 at 2:56 PM, Miroslav Balaz <gpsla...@googlemail.com>wrote: > >> but you need some kind of proof, for that.i alsow see from first sight >> that it is O(n^2), but i wane just fo verify that. >> >> 2009/4/1 Ajinkya Kale <kaleajin...@gmail.com> >> >>> I dont think you even need to solve the recursion .. >>> by looking at it it seems to be O(n^2) right ? >>> >>> >>> On Wed, Apr 1, 2009 at 2:18 PM, Miroslav Balaz >>> <gpsla...@googlemail.com>wrote: >>> >>>> no that is just asymptotic recursion. >>>> the answer is between n^2 and n^2log n >>>> >>>> of coure the answer is n^2; >>>> >>>> T(n)=n^2/2-n^2/4+n^2=n^2/4+n^2=T(n/2)+n^2=by master theorem n^2 >>>> >>>> T(n)< B(n)=2B(n/2)+n^2 what is by master theorem n^2 log n >>>> >>>> n >>>> n/2 n/2 >>>> n/4 n/4 n/4 n/4 >>>> >>>> T(n/2)=2T(n/4)-4T(n/8)+n^2/4 >>>> >>>> T(n)=4T(n/4)-8T(n/8)+n^2/2-4T(n/4)+n^2=-8T(n/8)+3n^2/2 >>>> >>>> you may pick up what is solution >>>> >>>> 2009/3/31 Arunachalam <arunachala...@gmail.com> >>>> >>>> What is the base value of this recursion? Without a base value the >>>>> recursion is not solvable? >>>>> >>>>> There should be some base value like T(x) = 1 where x <= 1. >>>>> >>>>> regards, >>>>> Arun. >>>>> >>>>> On Mon, Mar 30, 2009 at 12:35 AM, nikoo <shaker.far...@gmail.com>wrote: >>>>> >>>>>> >>>>>> Hello everybody >>>>>> >>>>>> I need the solution to the following recursion equation >>>>>> >>>>>> T(n) = 2 T (n/2) - 4 T (n/4) + n^2 >>>>>> >>>>>> does anybody know how to solve this equation? >>>>>> I appreciate any help >>>>>> >>>>>> thanks >>>>>> nikoo >>>>>> >>>>>> >>>>> >>>>> >>>>> -- >>>>> =================================== >>>>> want to know more about me >>>>> http"//ww.livejournal.com/users/arunachalam >>>>> >>>>> >>>>> >>>>> >>>> >>>> >>>> >>> >>> >>> -- >>> Ciao, >>> Ajinkya >>> >>> >>> >>> >> >> >> > > > -- > Ciao, > Ajinkya > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
