In this lesson on solving recurrence equations, the instructor teaches various methods of solving recurrence equations and emphasizes the importance of understanding these methods since they frequently arise in computer science applications, especially in dividing conquer algorithms. The methods include repeated substitution, the master theorem, change of variables, guessing the answer improving it by induction, linear homogenous equations, and diagonalization. The lesson includes examples of algorithms with the same recurrence equation, and the instructor demonstrates how to solve recurrence equations with big theta of n log n and big theta of n squared.
Learn some methods for attacking and solving recurrence equations.
More information about this course:
Licensed under Creative Commons Attribution ShareAlike 2.0: