Backward Substitution

Posted By on November 5, 2014


Download PDF
Forward Substitution
Problems that can be solved by Algorithms

Backward substitution, like forward substitution, tries to find a pattern from which we can guess a solution that we then prove using other techniques—but now we start with T(n) and expand it recursively using the recurrence.

For example, if we consider the same T(n) = T(n/2) + n recurrence from above, and assume for simplicity that n is a power of 2, then we get

  • T(n) = n + T(n/2) = n + n/2 + T(n/4) = n + n/2 + n/4 + T(n/8) = n + n/2 + n/4 + n/8 + T(n/16) = …

From this we might reasonably guess that T(n) is bounded by

[
sum_{i=0}^{infty} n/2^i
= n sum_{i=0}^{infty} 2^{-i}
= 2n.
]

 

Forward Substitution
Problems that can be solved by Algorithms

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