Calculating the Runtime of a Recursive Function

This lesson is about how to look at a recursive function and understand its runtime, which is not as immediately clear when you don’t have loops.

Runtime of recurring through a linked list

We have our pattern for recurring through a linked list:

def doSomething(self, node):
    if node is None:
        return
    # do something with the node
    self.doSomething(node.next)

Obviously, just like the iterative solution, this should be \(O(n)\). But how do we know for sure?

We can use a recurrence relation. First, just like with our loops, we define a function \(T(n)\), which represents the runtime of the recursive function for an input of size \(n\). The variable \(n\) in this case is the number of nodes in the linked list. However, we’re going to define \(T(n)\) recursively.

Let’s break down the doSomething function:

• Base Case: The function stops when node is None. This check and the return statement take a constant amount of time, which we can denote as \(O(1)\). This is our base case for the recurrence relation.

• Recursive Step: For each node, the function performs some constant-time work (the comment # do something with the node) and then makes a recursive call to self.doSomething(node.next). This recursive call is made on a subproblem of size \(n-1\) (the rest of the linked list). The constant work can be represented as \(c\).

Putting this together, the recurrence relation for the function is:

\[\begin{split} \begin{align} T(0) &= c_0\\ T(n) &= T(n-1) + c_1 \end{align} \end{split}\]

Here, \(T(0)\) is the base case when the list is empty (size 0), and \(T(n)\) represents the work for a list of size \(n\). The constant \(c_1\) represents the work done at each step (the if check and the “do something” part).

To solve this, we need to expand \(T(n)\) until it is no longer recursive. The steps to this are:

• Expand \(T(n)\) several times

• Write what the \(i\)th expansion would look like

• Calculate at which expansion you would reach the base case

• Write that final line of expansion

Let’s apply this approach to this recurrance relation. First, expand \(T(n)\) several times, and figure out what the \(i\)th expansion would be:

\[\begin{split} \begin{align} T(n) &= T(n-1) + c_1\\ &= (T(n-2) + c_1) + c_1 = T(n-2) + 2c_1\\ &= (T(n-3) + c_1) + 2c_1 = T(n-3) + 3c_1\\ &\vdots\\ &= T(n-i) + ic_1 \end{align} \end{split}\]

Then we calculate at which expansion we would reach the base case. We want the value of \(i\) where \(n-i=0\). This is, of course, when \(i=n\).

Then, we write this final line, by plugging in \(n\) for \(i\).

\[\begin{split} \begin{align} T(n) =& T(n-i)+ic_1\\ =& T(n-n)+nc_1\\ =& T(0)+nc_1\\ =& c_0+nc_1\\ \in& O(n) \end{align} \end{split}\]

We continue this process until we reach the base case, where \(n-k = 0\), which means \(k=n\). Substituting \(k=n\) back into our equation gives:

\[\begin{split} \begin{align} T(n) &= T(n-n) + nc_1\\ &= T(0) + nc_1\\ &= c_0 + nc_1 \end{align} \end{split}\]

Since \(c_0\) and \(c_1\) are constants, the term \(nc_1\) dominates as \(n\) grows. Therefore, the runtime of the function is \(O(n)\). This confirms our initial intuition that the recursive solution has the same linear time complexity as an iterative one for traversing a linked list.

Binary Search

To analyze the runtime of binary search, we define the recurrence relation \(T(n)\) for a sorted array of size \(n\).

• Base Case: When the search range is of size 1 (i.e., high - low == 1), the function performans constant work and returns, which we denote as \(O(1)\).

• Recursive Step: In each step, the algorithm checks the middle element. This is a constant amount of work. Then, it discards half of the search space and makes a recursive call on the remaining half. The size of the subproblem is halved at each step.

This leads to the following recurrence relation:

\[\begin{split} \begin{align} T(1) &= c_0\\ T(n) &= T(\frac{n}{2}) + c_1 \end{align} \end{split}\]

Here, \(T(1)\) is our base case for a single element, and \(T(n)\) represents the work for a search space of size \(n\). The constant \(c\_1\) represents the constant time operations performed at each step (e.g., calculating the middle index, comparing the values).

Now, let’s solve this recurrence. First we expand several times, and figure out what the \(i\)th expansion looks like:

\[\begin{split} \begin{align} T(n) &= T(\frac{n}{2}) + c_1\\ &= (T(\frac{n}{4}) + c_1) + c_1 = T(\frac{n}{4}) + 2c_1\\ &= (T(\frac{n}{8}) + c_1) + 2c_1 = T(\frac{n}{8}) + 3c_1\\ &\vdots\\ &= T(\frac{n}{2^i}) + ic_1 \end{align} \end{split}\]

Now we calculate what value of \(i\) would make \(\frac{n}{2^i}=1\), because that’s when we reach the base case. \(n=2^i\), so \(i=\log_2(n)\) (often denoted \(\lg n\)).

Substituting \(i = \lg n\) back into the equation:

\[\begin{split} \begin{align} T(n) &= T(\frac{n}{2^{\lg n}}) + (\lg n)c_1\\ &= T(1) + c_1 \lg n\\ &= c_0 + c_1 \lg n \end{align} \end{split}\]

Since \(c_0\) and \(c_1\) are constants, the dominant term is \(c_1 \lg n\). Therefore, the time complexity of the binary search algorithm is \(O(\log n)\).

Merge sort

Now, let’s explore a less obvious recursive algorithm called merge sort which, like bubble sort, is used to sort an array. This algorithm is similar to binary search in that it is recursive by nature.

The core idea of merge sort is to take an array, divide it in half, recursively sort each of those halves, and then merge the two sorted halves back together. Merging two already sorted lists is a straightforward process that can be done in linear time, or \(O(n)\).

The merge function below shows how this works. You simply walk down both lists, adding the smaller element from either list to a new, merged list.

def merge(left, right):
    merged = []
    left_index = 0
    right_index = 0

    # Merge the two halves in sorted order
    while left_index < len(left) and right_index < len(right):
        if left[left_index] <= right[right_index]:
            merged.append(left[left_index])
            left_index += 1
        else:
            merged.append(right[right_index])
            right_index += 1

    # Append any remaining elements
    merged.extend(left[left_index:])
    merged.extend(right[right_index:])

    return merged

The merge_sort function itself is quite simple and follows the exact logic described above:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    # Divide the array into two halves
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]
    # Recursively sort the two halves
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)
    # Merge the sorted halves
    return merge(left_half, right_half)

Take a moment to trace how this would sort a small array of eight numbers to fully grasp the process.

The full recurrence relation for mergesort is:

\[\begin{split} \begin{align} T(0) &= O(1)\\ T(1) &= O(1)\\ T(n) &= 2T(\frac{n}{2}) + O(n) \end{align} \end{split}\]

\[\begin{split} \begin{align} T(n) &= 2T(\frac{n}{2})+ cn\\ &= 2(2T(\frac{n}{4})+c\frac{n}{2})+cn\\ &= 4T( \frac{n}{4})+2cn\\ &= 4(2T(\frac{n}{8})+c\frac{n}{4}) + 2cn\\ &= 8T(\frac{n}{8})+3 cn\\ &= 2^iT(\frac{n}{2^i}) + icn \end{align} \end{split}\]

\(\frac{n}{2^i}=1\) when \(i=\lg n\).

\[\begin{split} \begin{align} T(n) =& 2^{\lg n}T(\frac{n}{2^{\lg n}}) + (\lg n)cn\\ =& nT(1) + c n\lg n\\ =& cn+cn\lg n\\ \in& O(n \lg n) \end{align} \end{split}\]

Merge sort has a time complexity of \(O(n \lg n)\). Better than bubble sort!