Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:chapter_fivesection_v [2012/03/13 02:17] – created mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chapter_fivesection_v [2012/03/13 02:22] (current) – [Designing the Algorithm] mugabej
@@ Line 9: / Line 9: @@
 \\
 The basic idea is to break up the product into partial sums.\\
-The recurrence relation of the algorithm: T(n) ≤ 4T(n/2) + cn\\
+The recurrence relation of the algorithm after some analysis: T(n) ≤ 3T(n/2) + cn\\
 ** Algorithm** \\
 \\
@@ Line 17: / Line 17: @@
 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>       y = y<sub>1</sub>*2^(n/2) + y<sub>0</sub>\\
 >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Compute x<sub>1</sub> + x<sub>0</sub> and y<sub>1</sub> + y<sub>0</sub>\\
->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> p = Recursive-Multiply(x<sub>1</sub> + x<sub>0</sub>,y<sub>1</sub> + >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> y<sub>0</sub>)\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> p = Recursive-Multiply(x<sub>1</sub> + x<sub>0</sub>,y<sub>1</sub> +  y<sub>0</sub>)\\
->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> x<sub>1</sub> y<sub>1</sub> = Recursive-Multiply(x<sub>1</sub>y<sub>1</sub>)\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> x<sub>1</sub> y<sub>1</sub> = Recursive-Multiply(x<sub>1</sub>,y<sub>1</sub>)\\
->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> x<sub>0</sub>y<sub>0</sub> = Recursive-Multiply(x<sub>0</sub>y<sub>0</sub>\\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> x<sub>0</sub>y<sub>0</sub> = Recursive-Multiply(x<sub>0</sub>,y<sub>0</sub>)\\
->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Return x<sub>1</sub>y<sub>1</sub>.(2^n) + (p - x<sub>1</sub>y<sub>1</sub> - >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> x<sub>0</sub>y<sub>0</sub>).(2^n/2) + x<sub>0</sub> y<sub>0</sub>
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> Return x<sub>1</sub>y<sub>1</sub>.(2^n) + (p - x<sub>1</sub>y<sub>1</sub> - \\
+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> x<sub>0</sub>y<sub>0</sub>).(2^n/2) + x<sub>0</sub> y<sub>0</sub>\\
+\\
+Upon analyzing this algorithm, we find out that the overall running time is O(n^(log(base 3)3)= O(n^1.59).\\
+\\
+I give this section 8/10