Lecture 8: Solving Recurrence Equations
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:
http://www.aduni.org/courses/discrete
Licensed under Creative Commons Attribution ShareAlike 2.0:
http://creativecommons.org/licenses/by-sa/2.0/
- Lecture Notes - Lecture Notes from the course
- Problem Set 4 - A problem set with some problems from this lecture
- Problem Set 4 Solutions - Solutions to the Problem Set
- Problem Set 4 Plus - A problem set with some problems from this lecture
- How do you solve recurrence equations?
- How do you use a divide and conquer algorithm to split a problem into two halves?
- What are some method for solving recurrence equations?
- How can you use repeated substitution to solve recurrence equations?
- What is the Master Theorem for solving divide and conquer recurrence equations, and how is it used instead of repeated substitution to analyze complexity more simply?
- How is change of variables used to solve recurrence equations?
- How can guessing the time complexity and proving by induction be used to solve recurrence equations?
- What are linear homogeneous equations and how can they be used to solve recurrence equations?
- How can you use Linear Algebra and diagonalization to solve recurrence equations?
- How do you find order, magnitude, or time complexity of sorts and other algorithms?
-
Staff Review
This lecture focuses on solving recurrence equations using a variety of different methods. The different methods and an explanation of how to use them and when they are useful are explained with a variety of problems in this lesson. Some really great example problems are done to solidify understanding of these concepts. For the most part, however, this video gets bogged down with a lot of really in-depth calculations. -
