Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2012:journals:jeanpaul:chapter_fivesection_ii [2012/03/11 23:09] – mugabej | courses:cs211:winter2012:journals:jeanpaul:chapter_fivesection_ii [2012/03/11 23:21] (current) – mugabej | ||
|---|---|---|---|
| Line 30: | Line 30: | ||
| We can find the the same bound using the substitution method as follows:\\ | We can find the the same bound using the substitution method as follows:\\ | ||
| We suppose T(n) ≤ qT(n/2) + cn and prove that we still get the same bound. See Book page 215-16 for complete proof.\\ | We suppose T(n) ≤ qT(n/2) + cn and prove that we still get the same bound. See Book page 215-16 for complete proof.\\ | ||
| - | + | \\ | |
| + | ** The Case of One Subproblem: | ||
| + | |||
| + | For q = 1, the total work spent on each level decreases as we run our recursion algorithm. After unrolling the algorithm, we find that in this case:\\ | ||
| + | Any T(.) satisfying the recurrence relation defined in the beginning paragraph of this section with q = 1 is bounded by O(n).\\ | ||
| + | |||
| + | ** A Related Recurrence: T(n) ≤ 2T(n/2) + O(n²)**\\ | ||
| + | \\ | ||
| + | On this class of problems, we spending O(n²) in recombining and divisions. After unrolling the recurrence relations, we find that:\\ | ||
| + | T(n) ≤ O(n²).\\ | ||
| + | \\ | ||
| + | I give this section 7/10 | ||
| + | | ||
