# What is an iterative method in Data structure and algorithm?

0 like 0 dislike
69 views

retagged

In this article ,you will know about

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

0 like 0 dislike
by (562 points)
selected

Best answer

# 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/2k)+1+1.....+1

( Put n/2k=1

⇒n=2k

⇒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)+32T(n/42)

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

⇒T(n)=n+(3/4)n+(3/4)2n+33T(n/43)

⇒n+3n/4+32n/42+.....+3lognø(1)

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

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

⇒T(n)≤n.4+O(n)

⇒T(n)=O(n)