What is an iterative method in Data structure and algorithm?

Question

In this article ,you will know about 

1. iterative method
2. How to solve problem by iterative method

Answer 1

Iterative Method

• In this method we dont have to guess the answer but it require more algebra than the substitution method.
• Hence, the recurrence is expanded or iterated so that it can be expressed as the summation of its term depend only on n and the initial condition.

P)Solve  T(n)=T(n/2)+1  if n>1

                          1              if n=1

Solution:

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

⇒T(n)=T(n/2²)+1+1

⇒T(n)=T(n/2^k)+1+1.....+1

  ( Put n/2^k=1

⇒n=2^k

⇒k=log n)

⇒T(n)=1+k=O(k)=O(log n)

P: 2) Solve T(n)=3T(n/4)+n

Solution:

T(n)=3T(n/4)+n

⇒T(n)=n+3(n/4)+3T(n/16))

⇒T(n)=n+3T(n/4)+3²T(n/4²)

⇒T(n)=n+3n/4+3²(n/16+3T(n/64))

⇒T(n)=n+(3/4)n+(3/4)²n+3³T(n/4³)

⇒n+3n/4+3²n/4²+.....+3^lognø(1)

⇒T(n)≤n+3n/4+3²/4+.....+3^lognø(1)

⇒T(n)≤n+3n/4+3²/4+....+n^log3

^{⇒T(n)≤n.4+O(n)}

⇒T(n)=O(n)

---