Solving recurrences is an art form. There are many techniques. One
of the simplest is to assume you know the form of the result with some
unknown coefficients. Then plug the form into the recurrence and try
to solve for the coefficients. If you succeed, you're done. If not,
look for another form or an entirely different technique.
Here we assume T(n) = an + b.
Substitute:
T(n) = an + b = 2T(n/2) + 2
= 2[ a(n/2) + b ] + 2
= an + 2b + 2
Now subtracting an+b from both sides we have b = -2.
To find a, we need the base case. With T(2) = 1, we have
T(2) = an + b = a(2) - 2 = 1
This produces a = 3/2, so T(n) = 3/2 n - 2 as stated.
On Nov 23, 3:59 am, Ankuj Gupta <[email protected]> wrote:
> When i try to solve this
>
> T(n) = 2T(n/2) + 2
>
> recurrence relation i get order N. But
>
> http://www.geeksforgeeks.org/archives/4583
>
> claims that it is 3/2n-2. The order is still N only but how do we get
> the constants ?
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
