Recurrence Relations to Recognize

Section 25.12 Recurrence Relations to Recognize

Now that we have analyzed factorial, we can apply the same logic to any other recursive function that does a constant amount of work per call and makes a single recursive call to repeat the process with one less than the current input. Any function that looks like:

🔗

int mystery(int n) {
    if (n <= 1) {
        // O(1) work
    } else {
        mystery(n - 1);
        // O(1) work
    }
}

will have the same recurrence relation as factorial:

\begin{equation*} T(n) = \begin{cases} O(1) & \text{if } n \leq 1 \\ T(n - 1) + O(1) & \text{if } n > 1 \end{cases} \end{equation*}

and thus will also have an overall time complexity of \(O(n)\text{.}\)

🔗

There are other common recurrence relations that we will see in recursive functions. Another common one is a function that makes a recursive call on half of the current input. For example, consider a function that looks like this:

🔗

int mystery(int n) {
    if (n <= 1) {
        // O(1) work
    } else {
        mystery(n / 2);
        // O(1) work
    }
}

This function has the recurrence relation:

\begin{equation*} T(n) = \begin{cases} O(1) & \text{if } n \leq 1 \\ T(n / 2) + O(1) & \text{if } n > 1 \end{cases} \end{equation*}

We will not go through the full solution here, but this recurrence relation solves to \(O(\log n)\text{.}\)

🔗

A final common recurrence relation is one where a function a linear (\(O(n)\)) amount of work and then makes two recursive calls on half of the current input. Here is an example of such a function:

🔗

int mystery(int n) {
    if (n <= 1) {
        // O(1) work
    } else {
        // O(n) work
        for (int i = 0; i < n; i++)...

        // Two recursive calls
        mystery(n / 2);
        mystery(n / 2);

        // O(1) work
    }
}

Here, the time to do a job of size \(n\) is the time to do two jobs of size \(n / 2\) plus \(O(n)\) work for the loop. This gives us the recurrence relation:

\begin{equation*} T(n) = \begin{cases} O(1) & \text{if } n \leq 1 \\ 2 \cdot T(n / 2) + O(n) & \text{if } n > 1 \end{cases} \end{equation*}

This recurrence relation solves to \(O(n \log n)\text{.}\)

🔗

You will not need to solve new recurrence relations for problems in this book. But you will need to recognize these common patterns:

🔗

Table 25.12.1. Recurrence Relations to Recognize

🔗

Pattern for General Case	Big-O	Description
\(T(n) = T(n / 2) + O(1) \)	\(O(\log n)\)	Function does constant work and makes a single recursive call on half the input. 🔗
\(T(n) = T(n - 1) + O(1) \)	\(O(n)\)	Function does constant work and makes a single recursive call on input reduced by one. 🔗
\(T(n) = 2 \cdot T(n / 2) + O(n) \)	\(O(n \log n)\)	Function does linear work and makes two recursive calls on half the input. 🔗

Checkpoint 25.12.1.

What pattern does the following function follow?

🔗

int mysteryFunction(int n) {
  if (n <= 1) {
    return 1;
  } else {
    int x = mysteryFunction(n - 1);
    return 2 * x;
  }
}

\(T(n) = T(n / 2) + O(1) \)
\(T(n) = T(n - 1) + O(1) \)
The function makes a single recursive call on input size n reduced by one. It only does a constant amount of work outside the recursive call.
\(T(n) = 2 \cdot T(n / 2) + O(n) \)

🔗

Checkpoint 25.12.2.

What pattern does the following function follow?

🔗

int mysteryFunction(int start, int end) {
  if (end > start + 1) {
    int mid = (start + end) / 2;
    mysteryFunction(start, mid);
    mysteryFunction(mid, end);
    for (int i = start; i < end; i++) {
      // do O(1) work
    }
  }
}

\(T(n) = T(n / 2) + O(1) \)
\(T(n) = T(n - 1) + O(1) \)
\(T(n) = 2 \cdot T(n / 2) + O(n) \)
The size here is \(n = end - start\text{.}\)

The function makes two recursive calls on half the input size and does linear work outside the recursive calls.

🔗

You have attempted of activities on this page.

🔗

Prev Top Next