Recurrence Questions
Given are some recurrence relations of the algorithm. You have to find "time Complexity" in the terms of 'n'.
1. T(n) = T(n - 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
These recurrence questions are solved by
1. Substitution Method - The substitution method comprises 3 steps1. Guess the form of the solution
2. Verify by Induction
3. Solve for constants.
We substitute the guessed solution for the function when applying the inductive hypothesis to smaller values. Hence the name "Substitution Method"
2. Iterative Method - This method first converts the recursion to a sum. To do this, repeat until the initial conditions are met. 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).
3. Recurrence Tree Method - The recursive tree method is a graphical representation of a tree-style iterative method that extends a node at each level. Generally, the second term of recurrence or f(n) is considered the root. This is useful when using the divide-and-conquer algorithm. Each route and child represents the cost of a single sub-problem.
4. Master's Theorem - It is a simplistic way to find time complexity. Question numbers 12 to 20 are solved by the master's theorem. Master's method works only for recurrence T(n) = aT(n/b) + f(n).
5. Extended Master's Theorem - Question no 12 to 25 will be solved by this theorem. But this is a very complex method. Most of the students try to solve questions number 12 to 20 with the master's theorem. This method will be used only for the recurrence T(n) = aT(n/b) + f(n), f(n) or running time, the log n value is used.
0 Comments