The Second method is the Iterative Method.
This method is excellent because by this method you can solve all the recurrence problems given in the Question on recurrence.
Iterative Method - It means to expand the recurrence and express it as a summation of terms of n and initial condition. T(1) was the required time in the initial state. To transform the recursion, first, decompose T(n) into T(n/2) and then T(n/4) and then up to T(1).
You will get all the 25 answers in the Question on recurrence.
1. T(n) = T(n - 1) + 1 T(1) = 1
2. T(n) = T(n - 1) + n
3. T(n) = T(n - 1) + n^2
4. T(n) = T(n - 1) + log n
5. T(n) = T(n - 1) + 1/n
6. T(n) = T(n - 1) + √n
7. T(n) = 2T(n - 1) + n
8. T(n) = T(n - 1) + 2^n
9. T(n) = 2T(n - 1) + 2^n
10. T(n) = 2T(n - 1) + log n
11. T(n) = √5 T(n - 1) + n
12. T(n) = T(n/2) + n
13. T(n) = 2T(n/2) + 1
14. T(n) = 2T(n/2) + n
15. T(n) = 4T(n/2) + n^2
16. T(n) = 3T(n/2) + n
17. T(n) = 2T(n/3) + n
18. T(n) = 7T(n/2) + n^2
19. T(n) = (5/2)T(3n/2) + n
20. T(n) = 2T(n/4) + √n
21. T(n) = T(n/2) + log n
22. T(n) = T(n/2) + n log n
23. T(n) = 2T(n/2) + log n
24. T(n) = 2T(n/2) + n log n
25. T(n) = 2T(n/2) + n/ log n
0 Comments