Design & Analysis Algorithms

Basic Recurrence

T(n) = aT(n/b) + f(n)
- a = number of subproblems
- b = subproblem size
- f(n) = cost of non-recursive work at each node

Size per node at level i

n/b^i

Number of nodes at level i

a^i

Cost per node at level i

f(n/b^i)

Total cost at level i

number of nodes * cost per node
a^i  * f(n/b^i)

Height of the tree

log_b(n)

Number of leaves

a^(log_b(n)) = n^(log_b(a))

Total cost of the entire recursion tree

T(n) = ∑ (from i = 0 to log_b(n)) [a^i * f(n/b^i)]