Substitution Method

  • The substitution method for solving recurrence relations consists of three steps:

    1. Guess the form of the solution.

    2. Verify by induction.

    3. Solve for constants.

  • Let’s take a look at an example. Suppose we want to solve T(n)=4T(n2)+nT(n) = 4T\left( \frac{n}{2} \right) + n.

    We will assume that T(1)=Θ(1)T(1) = \Theta(1).

    1. Let’s guess that T(n)∈O(n3)T(n) \in O(n^3). We will assume that T(k)≤ck3T(k) \leq ck^3 for k<nk < n.

    2. Now we need to prove that T(n)≤cn3T(n) \leq cn^3 by induction.

      The base case is T(n)=Θ(1)T(n) = \Theta(1) for all n<n0n < n_0 where n0n_0 is a suitable constant.

      We’ll now prove the general case.

      T(n)=4T(n2)+n≤4c(n2)3+n=(c2)n3+n=cn3−((c2)n3−n)≤cn3 \begin{aligned} T(n) &= 4T\left( \frac{n}{2} \right) + n \\ &\leq 4c\left( \frac{n}{2} \right)^3 + n \\ &= \left( \frac{c}{2} \right) n^3 + n \\ &= cn^3 - \left( \left( \frac{c}{2} \right) n^3 - n \right) \\ &\leq cn^3 \end{aligned}

      Our desired form was cn3cn^3, so we tried to put the equation in the form desired – residual: cn3−((c2)n3−n)cn^3 - \left( \left( \frac{c}{2} \right) n^3 - n \right). This is certainly less then our desired form cn3cn^3 whenever (c2)n3−n≥\left( \frac{c}{2} \right) n^3 - n \geq (residual), for example, if c≥2c \geq 2 and n≥1n \geq 1.

    3. For 1≤n<n01 \leq n < n_0, we have T(n)≤cn3T(n) \leq cn^3 if we pick cc large enough.

    And so we’ve shown that T(n)∈O(n3)T(n) \in O(n^3). But we can do better!

  • We shall now prove that T(n)∈O(n2)T(n) \in O(n^2).

    1. We’ll assume that T(k)≤ck2T\left(k \right) \leq ck^2 for k<nk < n.

    2. Now we need to prove this by induction. The base case is the same as before.

      Now we attempt to prove the inductive hypothesis.

      T(n)=4T(n2)+n≤4c(n2)2+n=(c2)n2+n=cn2−(−n) \begin{aligned} T(n) &= 4T\left( \frac{n}{2} \right) + n \\ &\leq 4c\left( \frac{n}{2} \right)^2 + n \\ &= \left( \frac{c}{2} \right) n^2 + n \\ &= cn^2 - \left( - n \right) \end{aligned}

      But there is no c>0c > 0 such that cn2−(−n)≤cn2cn^2 - \left( - n \right) \leq cn^2. It seems like we’ve hit a dead end! But we can actually strengthen the inductive hypothesis by subtracting a low-order term.

      Our new inductive hypothesis will be T(k)≤c1k2−c2kT(k) \leq c_1 k^2 - c_2 k for k<nk < n.

      T(n)=4T(n2)+n≤4(c1(n2)2−c2(n2))+n=c1n2−2c2n+n=c1n2−c2n−(c2n−n)≤c1n2−c2n if c2≥1. \begin{aligned} T(n) &= 4T\left( \frac{n}{2} \right) + n \\ &\leq 4 \left (c_1 \left( \frac{n}{2} \right)^2 - c_2 \left( \frac{n}{2} \right) \right) + n \\ &= c_1 n^2 -2c_2 n + n \\ &= c_1 n^2 - c_2 n - \left( c_2 n - n \right) \\ &\leq c_1 n^2 - c_2 n \text{ if } c_2 \geq 1. \end{aligned}

    3. We can pick c1c_1 large enough to handle the initial conditions.

  • As you can see, an important part of the substitution method involves making a good guess. But unfortunately, there is no general way to guess the correct solutions to recurrences. If a recurrence is similar to one you’ve seen before, then guessing a similar solution is reasonable.

results matching ""

    No results matching ""