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 > > > > > --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---