COMP1927 - Recurrence Relations and Complexity

We can use recurrence relations (recursive definitions of sequences) to work out the asymptotic complexity of various functions.

Examples

Linear Search

Linear Search is linear time (naturally), and the time taken to do n things is the time taken to do n-1 things, plus 1.

(1)
\begin{equation} T(n) = T(n-1) + 1 \end{equation}

Binary Search

Binary Searching on a list takes amount of time required to search a list of half that size, and then 1 more.

(2)
\begin{align} T(n) = T(\frac{n}{2}) + 1 \end{align}

Selection Sort

Selection Sort requires the list to be traversed fully n times. Hence n operations n times. SO to go up from an n-1 list requires another n operations.

(3)
\begin{equation} T(n) = T(n-1) + n \end{equation}

Insertion Sort

Insertion Sort requires (at worst case) 1 traversal with (well not quite but almost) n swaps at every element. (Hence O(n2). Essentially adding an extra element adds an extra n swaps.

(4)
\begin{equation} T(n) = T(n-1) + n \end{equation}

Merge Sort

Merge Sort requires the list to be halved down to single elements (e.g. 8 items need to be halved 3 times, or $log_2 8 = 3, \text{ or } 2^3 = 8$. So essentially 2k = n) (so the time it takes for each of those to happen). It then takes n comparisons to merge it back into a group.

(5)
\begin{align} \begin {array} \\ T(n) = T(\frac{n}{2}) + T(\frac{n}{2}) + n \\ T(n) = 2T(\frac{n}{2}) + n \\ \\ \text {Knowing that n actually takes } 2^k \text {times to halve it, we can substitute that for n} \\ \\ T(2^k) = 2T(2^{k-1}) + 2^k \\ \\ \text {If we then divide each term by } 2^k \text { we end up with a recurrence relation:} \\ \\ \frac{T(2^k)}{2^k} = \frac{T(2^{k-1})}{2^{k-1}} + 1 \\ \\ \text {Hence expanding that out a step we get that:} \\ \\ \frac{T(2^k)}{2^k} = \frac{T(2^{k-2})}{2^{k-2}} + 2 \\ \\ \text {Taking it another step further and expanding back k-1 steps (rather than 1):} \\ \\ \frac{T(2^k)}{2^k} = \frac{T(2^{k-k})}{2^{k-k}} + k \\ \\ \text {Which equals the more simple:} \\ \\ \frac{T(2^k)}{2^k} = T(1) + k \\ \frac{T(2^k)}{2^k} = k \\ \\ \text {And hence multiplying back by } 2^k \text {:} \\ \\ T(2^k) = k2^k \\ \\ \text {And back substituting k as lg(n):} \\ \\ T(n) = nlg(n) \end {array} \end{align}