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