Teaching Backward Substitution

A few times recently I have taught the upper-level undergraduate Algorithm Design And Analysis course at my institution. One of the goals of this course is being able to determine the cost (amount of work required) for algorithms whose work can be characterized by a recurrence relation.

I try to frame this as a fundamental skill for students, even to the point of having students characterize the work of iterative algorithms in a recursive manner (when possible) so that they can use the same framework they are learning about across lots of algorithms.

To actually turn the recurrence relations into closed form, I have, as of late, just focused on the methods of backward substitution¹, recurrence trees, and for appropriate recurrences, the Master Theorem.

This blog post will discuss my thoughts on teaching backward substitution, namely that:

• I try to get the students to see it as a 5-step process
• I give students practice with each step in isolation
• I assess students on individual steps and the whole process

The 5-step process

When I introduce backward substitution, I describe it as:

1. Expand the recurrence through rewrites
2. Find a pattern that emerges after several rewrites, where a variable \(i\) captures the number of rewrites that have occurred
3. Determine what is needed to make use of the initial condition
4. Substitute in information from the initial condition
5. Simplify

I note to the students that the two hardest steps are:

• Seeing the pattern (somewhat of an “art”, but gets easier with practice)
• Simplifying (familiarity with or the ability to look up rewriting rules, such as those for sums, makes this easier)

An example

In class and in my lecture notes, I will explicitly work through the individual steps of the 5-step process. For example, given a recurrence relation describing selection sort:

• \(T(n) = T(n-1) + (n-1)\)
• \(T(1) = 0\)

I show the following annotated steps:

Expand the recurrence through rewrites

• \(T(n) = T(n-1) + (n-1)\)
• \(T(n) = (T(n-2) + n-2) + (n-1)\)
• \(T(n) = ((T(n-3) + n-3) + (n-2)) + (n-1)\)

Find a pattern that emerges after several rewrites

• \(T(n) = T(n-3) + n + n + n - 3 - 2 - 1 \rightarrow T(n-3) + 3n - (3+2+1)\)
  • Also noting the previous rewrites had the form:
    • \(T(n-2) + 2n - (2+1)\)
    • \(T(n-1) + n- (1)\)
• \(T(n) = T(n-i) + i*n - \sum_{k=1}^{i} k\)

Determine what is needed to make use of the initial condition

To be able to plug in \(T(1)\) for \(T(n-i)\), we need \(i=n-1\).

Substitute in information from the initial condition

• \(T(n) = T(n-(n-1)) + (n-1)*n - \sum_{k=1}^{(n-1)} k\)
• \(T(n) = T(1) + (n-1)*n - \sum_{k=1}^{(n-1)} k\)
• \(T(n) = 0 + (n-1)*n - \sum_{k=1}^{(n-1)} k\)

Simplify

• \(T(n) = (n-1)*n - \sum_{k=1}^{(n-1)} k\)
• \(T(n) = n^{2}-n-\frac{n*(n-1)}{2}\)
• \(T(n) = n^{2}-n-\frac{n^{2}-n}{2}\)
• \(T(n) = \frac{n^{2}-n}{2}\)

Practice with and assessment of each step in isolation

I give the students practice with each step in isolation and also assess students both on individual steps and being able to complete the whole process. I think that assessing at the individual step level is important as it:

• Provides direct information on where students are having trouble
• Allows students to demonstrate they understand parts of the process
• Prevents a minor error early on from derailing the rest of a student’s work

Example practice problems

Here are a few examples of practice problems for the steps in isolation. These are typically done in class, so I can show the answer to one problem before proceeding to the next.

---

Setup: Assume a recurrence relation and base case as below. These formulas describe the number of comparisons required for determining if an even-length word is a palindrome.

• Recurrence relation: \(T(n) = T(n-2) + 1\)
• Base case: \(T(0) = 0\)

Problem 1: [Gives practice with: Expand the recurrence through rewrites] What are the new formulas that result from two additional rewrites of the recurrence relation?

Problem 2: (After students have seen the answer to Problem 1 above) [Gives practice with: Find a pattern that emerges after several rewrites] Given your above answers, is the following an appropriate pattern for the recurrence (a generalization of the work done so far):

\(T(n) = T(n-2i) + i\)

Problem 3: (After students have seen the answer to Problem 2 above) [Gives practice with: Determine what is needed to make use of the initial condition] Given the pattern above, using what value for \(i\) would allow us to rewrite the recurrence relation using the base case information?

---

Setup: Assume a recurrence relation and base case as below. These formulas describe the number of comparisons required for binary search.

• Recurrence relation: \(T(n) = T(\frac{n}{2}) + 2\)
• Base case: \(T(1) = 1\)

Problem 1: [Gives practice with: Expand the recurrence through rewrites] What are the new formulas that result from two additional rewrites of the recurrence relation?

Problem 2: (After students have seen the answer to Problem 1 above) [Gives practice with: Find a pattern that emerges after several rewrites] How can the following partial pattern be completed to reflect the rewrites above?

\(T(n) = T(\frac{n}{?}) + 2i\)

The incomplete part is the denominator of the fraction in \(T()\).

---

Setup: Consider the recurrence: \(T(n) = 2T(n-1) + 1\) and base case \(T(1) = 1\).

Problem: [Gives practice with: Find a pattern that emerges after several rewrites] Given the recurrence, here is the original recurrence which shows a first rewrite of \(T(n)\) to a formula based on \(T(n-1)\), followed by a second and third rewrite.

• \(T(n) = 2T(n-1) + 1\)
• \(T(n) = 2(2T(n-2) + 1) + 1 \rightarrow 4T(n-2) + 2 + 1 \rightarrow 4T(n-2) + 3\)
• \(T(n) = 2(2(2T(n-3) + 1) + 1) + 1 \rightarrow 8T(n-3) + 4 + 2 + 1 \rightarrow 8T(n-3) + 7\)

What is a pattern that represents the general nature of those rewrites? Work under the premise that the pattern should include \(T(n-i)\).

---

Setup: Consider the recurrence: \(T(n) = 2T(\frac{n}{2}) + (n-1)\) and base case \(T(1) = 0\).

Problem: [Gives practice with: Determine what is needed to make use of the initial condition] After multiple substitutions, assume that the pattern that is observed is:

\(T(n) = 2^{i}T(\frac{n}{2^{i}}) + in - (2^{i}-1)\)

What value should we use for \(i\) in order to be able to substitute in the base case?²

Footnotes

1. I also see this referred to as back substitution - not sure which is preferred - and I sometimes slip in an s, saying backwards substitution, though I’m not sure that is correct.

2. Note that this problem also implicitly gives the student another problem they can work on and check their work: getting from the recurrence relation in the setup to the pattern I provide.