The Masters Thm covers only a certain family of recurrences. There are many others.
Solving recurrences is comparable to finding analytical solutions to differential equations except that recurrences aren't as important in mathematical analysis, so aren't studied as much. I am not an expert, but there is a rich theory of generating functions that is widely regarded as a powerful tool for solving recurrences. The "guess and confirm" method that I described is covered in more detail in http://www.cs.uiuc.edu/~jeffe/teaching/algorithms/2009/notes/99-recurrences.pdf Gene On Nov 23, 12:58 pm, Ankuj Gupta <ankuj2...@gmail.com> wrote: > 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.
