T(n) = 4 * n^2 / 3 is a particular solution. You can see this by noting that it satisfies the equation.
You also need to find the general solution of T(n) = 2 * T(n/2) - 4 * T(n/4). Best I can figure, the general solution is: T(n) = a * [ ( 1 + i*sqrt(3) )^lg(n) + ( 1 - i*sqrt(3) )^lg(n) where i = sqrt(-1), a is an arbitrary constant determined by the initial conditions, and lg(.) is the base-2 logarithm function. The solution, which is the sum of the general solution and a particular solution, would be T(n) = a * [ ( 1 + i*sqrt(3) )^lg(n) + ( 1 - i*sqrt(3) )^lg(n) ] + 4 * n^2 / 3 I'm not at all sure that this is right, though. Nor do I see how to simplify it. Dave On Apr 1, 3:57 am, Ajinkya Kale <kaleajin...@gmail.com> wrote: > 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- Hide quoted text - > > - Show quoted text - --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
