Runtime Recurrence Relations

Tags

comp-sci

Some time-complexity calculations form as recurrence-relations, for [see page 13, example]:

\begin{align} T(n) &=

     \begin{cases}
       \theta(1) & \text{if \\( n = 2^0 = 1 \\)} \\\\
       2T(\frac{n}{2}) + \theta(n) & \text{if \\( n = 2^k \\) for \\( k \geq 1 \\)}
     \end{cases}

\end{align}

These can be solved in 3 ways: substitution method, recursion tree, master theorem.

Substitution Method

Involves guessing a solution for the time-complexity and then verifying through induction.

Recursion Tree

Draw a [see page 14, recursion-tree] and then add times across the tree.

Master Theorem

Follows the form \( T(n) = aT(\frac{n}{b}) + f(n) \).