Recurrence Relations

Table of contents

1. Binary search (intuitive)
2. Binary search
3. Unrolling recurrences
4. Merge operation
5. Merge sort walkthrough
6. Merge sort
7. Merge sort analysis
8. Recurrence diagrams
9. Common recurrences
10. method1
11. g0
12. help

Binary search (intuitive)

Binary search

Let’s re-analyze the runtime for binary search on a sorted array, but this time looking at the recursive implementation. The binarySearch method below returns the index of the search target or -1 if the target is not in the sorted array.

static int binarySearch(int[] sorted, int target) {
    return binarySearch(sorted, target, 0, sorted.length);
}

static int binarySearch(int[] sorted, int target, int low, int high) {
    if (low > high) {
        return -1;
    }
    int mid = low + (high - low) / 2;
    if (sorted[mid] < target) {
        return binarySearch(sorted, target, mid + 1, high);
    } else if (sorted[mid] > target) {
        return binarySearch(sorted, target, low, mid - 1);
    } else {
        return mid;
    }
}

It turns out that the worst-case order of growth of the runtime for binarySearch is logarithmic with respect to the length of the sorted array. In each recursive call of the loop, half of the remaining elements under consideration can be ignored. In other words, the number of recursive calls is given by the answer to the question, “How many times do we need to divide N (length of the sorted array) by 2 until only 1 element remains?” This is the definition of the binary logarithm (log₂ or simply lg).

Logarithm base

Computer scientists often don’t specify the logarithm base. A common assumption is to work in base-2 (binary logarithm) since it corresponds to how bits are represented in a computer. For the purpose of asymptotic analysis, the log base doesn’t affect the result because all log bases are within a constant multiplicative factor of each other.

How might we prove that the worst-case order of growth of the runtime of binarySearch is in Θ(log N)? We have a formal, mathematical definition for big-theta notation, so it’s nice to be able to use it!

Recurrence relations are recursive functions that model non-recursive work and recursive work.

Recurrence relation for the worst-case runtime of binarySearch

T(N) = T(N/2) + c for N > 1

T(1) = d

c represents the constant time spent on non-recursive work, such as comparing low < high, computing mid, and comparing the target with sorted[mid]. T(1) = d represents the base case, which takes a different amount of constant time to compare low < high and immediately return -1. The time spent on recursive work is modeled by T(N/2) because a recursive call to binarySearch will examine either the lower half or upper half of the remaining N items.

Our goal is to rewrite this recurrence relation in a closed-form expression that’s compatible with asymptotic notation definitions. One approach is to unroll the recurrence: plug the recurrence back into itself until the recursion is done.

• T(N) = T(N/2) + c
• T(N) = T(N/4) + c + c
• T(N) = T(N/8) + c(3)
• …
• T(N) = T(N/N) + c(log N)
• T(N) = d + c(log N)

We can then apply big-theta notation to describe the order of growth of the closed-form expression for T(N), the worst-case runtime of binarySearch.

Unrolling recurrences

While this course is not focused too heavily on the mathematics behind solving recurrences, it’s useful to have an intuitive understanding of a recurrence relation and be able to compute basic closed-form solutions. Recognize and apply these two identities to simplify a series.

1 + 2 + 3 + 4 + … is approximately the square of the last term: 1 + 2 + 3 + 4 + ⋯ + N = N(N + 1) / 2. For a visualization of this identity, look back at our worst-case asymptotic runtime analysis of dup1.

1 + 2 + 4 + 8 + … is 1 less than double the last term: 2⁰ + 2¹ + ⋯ + 2^k = 2^k + 1 − 1.

WolframAlpha can compute the asymptotic bound for any recurrence relation, e.g. T(N) = T(N / 2) + 1. Did you recognize this recurrence as binary search? As you get more familiar with recurrences, you’ll start to see them more and more often.

For these questions, consider the recurrence relation T(N) = T(N/2) + cN and T(1) = d.

Question 1

Which of the following variants of binarySearch could have a runtime represented by the recurrence relation?

• Recursive binarySearch as presented earlier.
• Recursive binarySearch but also printing out the value of sorted[mid].
• Recursive binarySearch but also printing out the range of values sorted[low] to sorted[high].
• Recursive binarySearch but also printing out the entire sorted array.

Question 2

Unroll the recurrence and identify the big-theta asymptotic bound.

• Θ(1)
• Θ(log N)
• Θ(N)
• Θ(Nlog N)

Merge operation

Merge is an algorithm building-block for merge sort, our next case study for recurrence relations.

Question 1

What is the overall order of growth for the runtime of merge with respect to N, the total number of items in both of the sorted arrays?

• Θ(1)
• Θ(log N)
• Θ(N)
• Θ(Nlog N)

Merge sort walkthrough

Merge sort

Merge sort is a recursive sorting algorithm that we’ll use as a case study of recurrence relations. It relies on the merge operation, which takes two sorted arrays and returns a sorted result containing all of the items in both of the given arrays.

Merge sort

1. If the array is of size 1, return.
2. Recursively merge sort the left half.
3. Recursively merge sort the right half.
4. Merge the two sorted halves.

Recurrence relation for the runtime of merge sort

T(N) = T(N/2) + T(N/2) + c₁N + c₀ for N > 1

T(1) = d

Each call to merge sort makes two recursive calls to subproblems of half the size each and then spends linear time merging the sorted halves. Unrolling this recurrence is a bit trickier since there are two recursive branches. Another approach is to draw a recurrence diagram that represents the recursive work and non-recursive work in the recurrence relation!

The top layer takes about 64 units of time merging two sorted halves of 32 items each. The second layer also takes about 64 units to time merging four sorted halves of 16 items each. By identifying the pattern in the recurrence diagram, we can see that each level will take about 64 units of time.

Level

All of the nodes at the same depth (number of edges) from the overall root.

Since the entire runtime of merge sort is represented by this diagram, we can find the total time spent by multiplying the number of levels in the tree by the time spent on each level. Each level divides the input size in half until the base case of 1 item is reached so there are log₂N levels. Each level takes about N time to merge many small arrays. Overall, the order of growth of the runtime for merge sort is in N log₂N.

Merge sort analysis

Recurrence diagrams

Merge sort is an example of a work-per-level recurrence. We found that each level in the recurrence diagram performed roughly the same amount of (non-recursive) work. The sum of all of the levels resulted in the total amount of time merge sort takes to run, including all recursive work (each node in the diagram) and all of the non-recursive work (the merge operation). Two big assumptions enabled us to use multiplication as a shortcut to simplify the final result.

1. What is the (non-recursive) work done by each node on level i? How many total nodes are on each level i? Assumption 1: Each node on level i performs the same amount of work, so we can multiply the work per node by the number of nodes on that level.
2. What is the total (non-recursive) work done on level i? How many levels are in the tree? Assumption 2: Each level performs the same amount of work, so we can multiply the work per level by the number of levels to get the total runtime of the entire recurrence.

Even when these assumptions don’t hold, we can still go back to writing out the sum of the terms instead of using multiplication as a shortcut. Work-per-node recurrences represent a category of recurrences that don’t meet assumption 2. Consider f3.

static int f3(int n) {
    if (n <= 1)
        return 1;
    return f3(n - 1) + f3(n - 1);
}

Question 1

Give a recurrence relation for the runtime of f3. Try drawing out the first couple levels of the recurrence diagram!

Question 2

What is the (non-recursive) work done by each node on level i?

• Constant
• Logarithmic with respect to the size of the current subproblem.
• Linear with respect to the size of the current subproblem.

Question 3

How many total nodes are on each level i?

Assume the overall root node is at level 0, its immediate children at level 1, and so forth.

• 1
• i
• 2i
• 2ⁱ

Question 4

Although assumption 1 is true and we can multiply the answers to the above two questions to get the work-per-level, we’ll see that the work-per-level is not all the same.

Give a closed-form expression for T(N) as a sum of all of the levels in the recurrence diagram. For simplicity, replace the constants c and d with 1.

Then, apply a mathematical identity to find a simple big-theta runtime bound.

Common recurrences

Here’s a list of common recurrences and their simplified big-theta asymptotic bounds.

Single recursion

• T(N) = T(N/2) + 1 ∈ Θ(log N)
• T(N) = T(N − 1) + 1 ∈ Θ(N)
• T(N) = T(N/2) + N ∈ Θ(N)
• T(N) = T(N − 1) + N ∈ Θ(N²)

Multiple recursion

• T(N) = 2T(N/2) + 1 ∈ Θ(N)
• T(N) = 2T(N − 1) + 1 ∈ Θ(2^N)
• T(N) = 2T(N/2) + N ∈ Θ(Nlog N)
• T(N) = 2T(N − 1) + N ∈ Θ(2^N) solved on the Math Stack Exchange

method1

Consider the following method.

static int method1(int N) {
  if (N <= 1) {
      return 1;
  } else {
      int a = method1(N - 1);
      int b = method1(N - 1);
      int c = method1(N - 1);
      return a + b + c;
  }
}

Question 1

Give a recurrence relation that describes the runtime of method1.

Question 2

True/False: If we solved the recurrence diagram, we can use assumption 1 in a work-per-level analysis.

Assumption 1

Each node on level i performs the same amount of work, so we can multiply the work per node by the number of nodes on that level.

Question 3

True/False: If we solved the recurrence diagram, we can use assumption 2 in a work-per-level analysis.

Assumption 2

Each level performs the same amount of work, so we can multiply the work per level by the number of levels to get the total runtime of the entire recurrence.

g0

Consider the following method. Assume k(N) runs in constant time and returns a boolean.

static void g0(int N) {
    if (N == 0)
        return;
    g0(N / 2);
    if (k(N))
        g0(N / 2);
}

Question 1

True/False: In the best-case runtime analysis for g0, k(N) always returns false.

Question 2

Identify the best-case order of growth for the runtime of g0 with respect to N.

• Θ(1)
• Θ(log N)
• Θ(N)
• Θ(Nlog N)
• Θ(N²
• Θ(N²log N)
• Θ(N³)

Question 3

Identify the worst-case order of growth for the runtime of g0 with respect to N.

• Θ(1)
• Θ(log N)
• Θ(N)
• Θ(Nlog N)
• Θ(N²
• Θ(N²log N)
• Θ(N³)

help

Consider the following method.

static int help(int N) {
    if (N < 1000) {
        for (int i = 0; i < N * N * N; i += 1)
            System.out.print("be");
        return x;
    } else {
        for (int i = 0; i < N / 2; i += 1)
            System.out.print("be");
        return 2 * help(N / 2);
    }
}

Question 1

True/False: In the best-case runtime analysis for help, N is less than 1000.

Question 2

Give the order of growth for the runtime of help with respect to N.

• Θ(1)
• Θ(log N)
• Θ(N)
• Θ(Nlog N)
• Θ(N²
• Θ(N²log N)
• Θ(N³)
• Θ(2^N)