SUMMER TRAINING Free Tutorials  Go To Your University  Placement Preparation 
Project Based Best Summer Training Courses in Jaipur
Join our Telegram Channel To take free Online Courses
0 like 0 dislike
69 views
in Examples, Exercises and Projects by (562 points)
retagged by

In this article ,you will know about 

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

1 Answer

0 like 0 dislike
by (562 points)
selected by
 
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)


Our Mentors(For AI-ML)


Sharda Godara Chaudhary

Mrs. Sharda Godara Chaudhary

An alumna of MNIT-Jaipur and ACCENTURE, Pune

NISHA (IIT BHU)

Ms. Nisha

An alumna of IIT-BHU

 Goeduhub:

About Us | Contact Us || Terms & Conditions | Privacy Policy || Youtube Channel || Telegram Channel © goeduhub.com Social::   |  | 
...