Differences
This shows you the differences between two versions of the page.
| |
| courses:cs211:winter2018:journals:holmesr:section_5.2 [2018/03/14 02:17] – created holmesr | courses:cs211:winter2018:journals:holmesr:section_5.2 [2018/03/14 03:07] (current) – holmesr |
|---|
| ====== Section 5.2 Further Recurrence Relations ====== | ====== Section 5.2 Further Recurrence Relations ====== |
| |
| This section explores a more general version of recurrence problem than the previous one did. This type of recurrence creates recursive calls on q subproblems of size n/2. Mergesort uses q = 2, but can in fact be 1 or >2. Geberalizing the inequality from the previous section gives us: T(n) <= qT(n/2) + cn when n > 2. | This section explores a more general version of recurrence problem than the previous one did. This type of recurrence creates recursive calls on q subproblems of size n/2. Mergesort uses q = 2, but can in fact be 1 or >2. Generalizing the inequality from the previous section gives us: T(n) <= qT(n/2) + cn when n > 2. |
| |
| For more than 2 subproblems, | For algorithms that split the input into more than 2 subproblems we can still use the same unrolling technique discussed in the previous section. Consider a problem where q = 3. The first level will have 1 problem of size n, which will be split into 3 problems of size n/2, which is then split into 9 problems of size n/4 and so on. This makes it obvious that work is increasing throughout the running of the problem. To identify the pattern, we can notice that the number of problems per level is simply our q (3) raised to the power which is equal to the level number. Additionally, the size of each problem is n/(2<sup>r</sup>) where r is the number of the level. Finally, summing over the levels of recursion, we can say that any function satisfying the inequality mentioned in the first paragraph with q > 2 is bounded by O(n<sup>log<sub>2</sub>q</sup>). |
| | |
| | Again the section mentions an alternative method of finding the bound using partial substitution, but I can't honestly say that I understand how this method adds anything that unrolling the substitution will not. |
| | |
| | Another case to be considered is one where q = 1. In the first level, there is one problem of size n. Then one problem of size n/2, then one problem of size n/4 and so on down the line. We can see that the amount of work is decreasing. It is clear from analyzing just these few levels that layer r will have size n/2<sup>j</sup> and it will contribute cn/2<sup>j</sup> to the running time. Finally, summing the levels of recursion will give us T(n) <= 2cn = O(n). Thus, any T satisfying the inequality from paragraph 1 with q = 1 is bounded by O(n). |
| | |
| | It is interesting to note these differences in running times all fall around q = 2, with radically different behavior observed when q = 1 and when q = 3. It leads me to wonder what happens when q is a non-integer number between 1 and 2. |
| | |
| | Finally, we can consider what happens in the case that the algorithm "divides up the input into two different pieces of size n/2, solves the subproblems by recursion, and then combines the two into an overall solution, spending quadratic time instead for the initial division and final recombining." This is different from the problems such as mergesort since it takes quadratic time for the division and recombining instead of linear. So the problems take this form: T(n) <= 2T(n/2) + cn<sup>2</sup>. Instinctively, one would like to say that this should be bounded by O(n<sup>2</sup> log n) however it is actually bounded by O(n<sup>2</sup>) due to how quickly n<sup>2</sup> decreases as it is replaced with n/(2<sup>j</sup>) |
