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 of videos where I solve recurrence relations and perform algorithm analysis on code that anyone can check out for free !

Image for post
Image for post

Thanks for reading this article I hope its helpful to you all ! Keep up the learning, and if you would like more computer science, programming and algorithm analysis videos please visit and subscribe to my YouTube channels (randerson112358 & compsci112358 )

Image for post
Image for post
https://youtu.be/ArlyWwygMkk

Check Out the following for content / videos on Computer Science, Algorithm Analysis, Programming and Logic:

YouTube Channel:
randerson112358: https://www.youtube.com/channel/UCaV_0qp2NZd319K4_K8Z5SQ

compsci112358:
https://www.youtube.com/channel/UCbmb5IoBtHZTpYZCDBOC1CA

Website:
http://everythingcomputerscience.com/

Video Tutorials on Recurrence Relation:
https://www.udemy.com/recurrence-relation-made-easy/

Video Tutorial on Algorithm Analysis:
https://www.udemy.com/algorithm-analysis/

Twitter:
https://twitter.com/CsEverything

YouTube Channel:

Image for post
Image for post

Computer Science Website:

Image for post
Image for post

Udemy Videos on Algortithm Analysis:

Image for post
Image for post

Resources:
http://www.cs.cornell.edu/courses/cs211/2005sp/Lectures/L14-BigO/L14-15-Complexity.4up.pdf

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store