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)
$$T(n) = T(n-1) + 1$$

## 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)
$$T(n) = T(n-1) + n$$

## 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)
$$T(n) = T(n-1) + n$$

## 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}
page revision: 6, last edited: 10 Sep 2011 03:22