Thanx Gene. Is there any other method than master's thm ? On Nov 23, 4:13 pm, Gene <gene.ress...@gmail.com> wrote: > 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 <ankuj2...@gmail.com> 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 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?hl=en.
