Yes you are right Miroslav ... that was a pretty dumb mistake i made :) On Wed, Apr 1, 2009 at 9:25 PM, Miroslav Balaz <gpsla...@googlemail.com>wrote:
> 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 >> >> >> > > > > -- 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 -~----------~----~----~----~------~----~------~--~---
