Recurrence Relation Cheat Sheet

Easily Solve Common Recurrences

Have you found it hard to solve the time complexity of recurrence relations ? I will show you how to solve some of the most common recurrence relations fast and easily without using any techniques other than memorization.

Below are the common recurrences.

Note: a, b, d and k are all constant values.

1. T(n) = T(n-1)+b, T(1) = a
   T(n) = O(n)
2. T(n) = T(n-1) + bn, T(1) = a
   T(n) = O(n²)
3. T(n) = T(n/2) + b, T(1) = a
   T(n) = O( log n)
4. T(n) = T(n/2) + bn, T(1) = a
   T(n) = O(n)
5. T(n) = kT(n/k) + b, T(1) = a
   T(n) = O(n)
6. T(n) = kT(n/k) + bn, T(1) = a
   T(n) = O(n log n)
7. T(n) = T(n-1) + T(n-2) + d, T(1) = a, T(2) = b
   T(n) = O(2^n)
8. T(n) = T(n-1) + b n^k, T(1) = a
   T(n) = O(n^(k+1))

If you would like to learn more about Algorithm Analysis , you can take my online course here. I also have a course on Udemy.com called Recurrence Relation Made Easy where I help students to understand how to solve recurrence relations and asymptotic terms such as Big-O, Big Omega, and Theta. You can check out my YouTube channel…