### 2 videos in "Recurrence Equations"

## Lecture 8: Solving Recurrence Equations

Lecture 8: Solving Recurrence Equations

6847 views, 3 ratings - 01:10:21

Part of video series ArsDigita Discrete Math Course

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/

http://www.aduni.org/courses/discrete

Licensed under Creative Commons Attribution ShareAlike 2.0:

http://creativecommons.org/licenses/by-sa/2.0/

(
download video
)

Learn some methods for attacking and solving recurrence equations.

- Lecture Notes - Lecture Notes from the course
- Problem Set 4 - A problem set with some problems from this lecture
- Problem Set 4 Plus - A problem set with some problems from this lecture
- Problem Set 4 Solutions - Solutions to the Problem Set

- 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?

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.

This is the most thorough video I've found on the web regarding recurrence equations.