How do you pick variable substitutions in recurrence relations?

Question

In our Data Structures class we are learning how to solve recurrence relations in 1 variable. Unfortunately some things seem to come "out of the blue".

For example, some exercises already tell you how to substitute the variable n:

Compute T(n) for n = 2^k

• T(n) = a for n =< 2

• T(n) = 8T(n/2) + bn^2 (a and b are > 0)

But some exercises just give you the T(n) without providing a replacement for the variable n:

• T(n) = 1 n =<1

• T(n) = 2T(n/4) + sqrt(n)

I used the iterative method and arrived to the right answer: sqrt(n) + (1/2) * sqrt(n) * Log(n).

But when the professor explained she started by saying: "Let n = 4^k", which is what I mean by "out of the blue". Using that fact the answer is simpler to obtain.

But how is the student supposed to come up with that?

This is another example:

• T(n) = 1 n =<1

• T(n) = 2T( (n-1)/2 ) + n

Here I started again with the iterative method but I can't reach a definitive answer, it looks more complex that way. After 3 iterative steps I arrived to this:

1. T(n) = 4T( (n-2)/4 ) + 2n - 1

2. T(n) = 8T( (n-3)/8 ) + 3n - 3

3. T(n) = 16T( (n-4)/16 ) + 4n - 6

I am inclined to say T(i) = 2^i * T( (n-i)/2^i ) + i*n - ? This last part I can't figure out, maybe I made a mistake.

However in the answer she provides she starts again with another substitution: Let n = (2^k) -1. I don’t see where this comes from - why would I do this? What is the logic behind that?

Answer 1

In all of these cases, these substitutions are reasonable because they rewrite the recurrence as one of the form S(k) = aS(k - 1) + f(k). These recurrences are often easier to solve than other recurrences because they define S(k) purely in terms of S(k - 1).

Let's do some examples to see how this works. Consider this recurrence:

T(n) = 1 (if n ≤ 1)

T(n) = 2T(n/4) + sqrt(n) (otherwise)

Here, the size of the problem shrinks by a factor of four on each iteration. Therefore, if the input is a perfect power of four, then the input will shrink from size 4^k to 4^k-1, from 4^k-1 to 4^k-2, etc. until the recursion bottoms out. If we make this substitution and let S(k) = T(4^k), then we get hat

S(0) = 1

S(k) = 2S(k - 1) + 2^k

This is now a recurrence relation where S(k) is defined in terms of S(k - 1), which can make the recurrence easier to solve.

Let's look at your original recurrence:

T(n) = a (for n ≤ 2)

T(n) = 8T(n/2) + bn²

Notice that the recursive step divides n by two. If n is a perfect power of two, then the recursive step considers the power of two that comes right before n. Letting S(k) = T(2^k) gives

S(k) = a (for k ≤ 1)

S(k) = 8S(k - 1) + b2^2k

Notice how that S(k) is defined in terms of S(k - 1), which is a much easier recurrence to solve. The choice of powers of two was "natural" here because it made the recursive step talk purely about the previous value of S and not some arbitrarily smaller value of S.

Now, look at the last recurrence:

T(n) = 1 (n ≤ 1)

T(n) = 2T( (n-1)/2 ) + n

We'd like to make some substitution k = f(n) such that T(f(n)) = 2T(f(n) - 1) + n. The question is how to do that.

With some trial and error, we get that setting f(n) = 2ⁿ - 1 fits the bill, since

(f(n) - 1) / 2 = ((2ⁿ - 1) - 1) / 2 = (2ⁿ - 2) / 2 = 2^n-1 - 1 = f(n) - 1

Therefore, letting k = 2ⁿ - 1 and setting S(k) = T(2ⁿ - 1), we get

S(n) = 1 (if n ≤ 1)

S(n) = 2S(n - 1) + 2ⁿ - 1

Hope this helps!