Forward Substitution

Posted By on November 5, 2014


Download PDF
Time Complexity
Backward Substitution

Forward substitution

Let’s consider the recurrence

  • T(n) = T(n-1) + 2n – 1
  • T(0) = 0

The method of forward substitution proceeds by generating the first half-dozen or so terms in the sequence described by the recurrence, in the hope that it will turn out to be a sequence we recognize. In this case, we can calculate

  • n

    T(n)

    0

    0

    1

    1

    2

    4

    3

    9

    4

    16

    5

    25

and at this point we can shout “Aha! This example was carefully rigged to give T(n)=n²!”. Unfortunately, there are infinitely many sequences that start with these six numbers, so we can’t be fully sure that this is the right answer until we prove it. So let’s do so.

We will show that T(n) = n² satisfies the above recurrence for all n, by induction on n. The base case is n = 0; here T(0) = 0 = 0². For n > 0, we have

  • T(n) = T(n-1) + 2n – 1 = (n-1)² + 2n – 1 = n² – 2n + 1 + 2n – 1 = n²,

and we are done.

(Here we used the induction hypothesis where we replace T(n-1) by (n-1)². We will usually not be very explicit about this.)

Here’s a less rigged example:

  • T(n) = T(floor(n/2)) + n, T(0) = 0.

Computing small cases gives

  • n

    T(n)

    0

    0

    1

    1

    2

    3

    3

    4

    4

    7

    5

    8

    6

    10

    7

    11

    8

    15

which doesn’t really tell us much about the behavior for large values. We can easily add a few powers of 2 to get an idea of what happens later:

  • 16

    31

    32

    63

    64

    127

From this we might guess that the solution satisfies T(n) <= 2n (or perhaps T(n) <= 2n – 1 for n > 0). So let’s see if we can prove it:

Base case

T(0) = 0 <= 2n.

Induction step

For n > 0, T(n) = T(floor(n/2) + n <= 2 floor(n/2) + n <= 2(n/2) + n = 2n.

We might be able to prove a slightly tighter bound with more work, but this is enough to sho T(n) = O(n). Showing that T(n) = Omega(n) is trivial (since T(n) >= n), so we get T(n) = Θ(n) and we are done.

Applying the method of forward substitution requires a talent for recognizing sequences from their first few elements. If you are not born with this talent, you can borrow it from the mathematician Neal J. A. Sloane, or at least from his on-line

Time Complexity
Backward Substitution

Download PDF

Posted by Akash Kurup

Founder and C.E.O, World4Engineers Educationist and Entrepreneur by passion. Orator and blogger by hobby

Website: http://world4engineers.com