Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:chapter_fivesection_ii [2012/03/11 22:40] – mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapter_fivesection_ii [2012/03/11 23:21] (current) – mugabej
@@ Line 7: / Line 7: @@
 **The case of q>2 Subproblems: ** \\
 \\
-  ** Analyzing the first few levels:\\
+  *Analyzing the first few levels:\\
->>>>>>>>>>>>>>>>>>>>>>>> At the first level, we have a single problem of size n. Takes at most cn time + time spent in subsequent recursive class.\\
+At the first level, we have a single problem of size n. Takes at most cn time + time spent in subsequent recursive calls.\\
 >>>>>>>>>>>>>>>>>>>>>>>> The following level has q problems, each of size n/2. Each of these problems costs at most cn/2 for a total of at most (q/2)*cn + time spent in subsequent recursive calls.\\
 >>>>>>>>>>>>>>>>>>>>>>>> The next level has q² problems, each of size n/4. Each of these problems costs at most cn/2 for a total of at most (q²/4)*cn + time spent in subsequent recursive calls.\\
 >>>>>>>>>>>>>>>>>>>>>>>> SO the total work per level is increasing as the algorithm is executed.\\
+  * Identifying a pattern:\\
+>>>>>>>>>>>>>>>>>>>>>>>> At any given level j, we have q^j distinct problems, each of size n/(2^j).\\
+>>>>>>>>>>>>>>>>>>>>>>>> Thus the total time at any level j is (q^j)(cn/(2^j))= [(q/2)^j]*cn\\
+\\
+  * Summing over all levels of recursion:\\
+>>>>>>>>>>>>>>>>>>>>>>>> There are log(in base 2)(n)levels of recursion.\\
+>>>>>>>>>>>>>>>>>>>>>>>> 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)).\\
+\\
+** 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