Table of Common Recurrence Relations

binary search
sequential search
tree traversal
quick select
mergesort, quicksort
Insertion or selection sort

Quick Bits

  • where is almost always .

Master Theorem

See Master theorem (analysis of algorithms) - Wikiwand ⇒ Can be used to solve most recurrence relations.

First, Identify the recurrence relation in the following form

Consider three casesp

  • Case 1:
  • Case 2:
  • Case 3:

Recurrence Tree