Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2012:journals:jeanpaul:chapter_fivesection_ii [2012/03/11 23:03] – mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapter_fivesection_ii [2012/03/11 23:21] (current) – mugabej
@@ Line 23: / Line 23: @@
 >>>>>>>>>>>>>>>>>>>>>>>> After some calculations, we find that the overall running time is:\\
 >>>>>>>>>>>>>>>>>>>>>>>> T(n) = O([n^(log(in base 2) q)])\\
->>>>>>>>>>>>>>>>>>>>>>>> So,the generalization is:Any T(.) that satisfies the recurrence relation we cited in the beginning paragraph with q>2 is bounded by O(n^(log(in base2)q)).\\
+>>>>>>>>>>>>>>>>>>>>>>>> So,the generalization is:\\
+>>>>>>>>>>>>>>>>>>>>>>>> Any T(.) that satisfies the recurrence relation we cited in the beginning paragraph with q>2 is bounded by O(n^(log(in base2)q)).\\
 \\
+** Applying Partial Substitution** \\
+\\
+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.\\
+\\
+** 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