-
- Find formulas for a three parts Karatsuba's trick.
Using MAPLE or AXIOM, for setting up these formulas, would
be a good idea.
-
- Is this three parts Karatsuba's trick theoretically better
than the usual two parts one?
That is, does this lead to a better time complexity
upper bound?
You will need the so-called Master Theorem
for analyzing the complexity of divide-and-conquer algorithms.
See the document Master Theorem: Practice Problems and Solutions
posted on our web site.
Marc Moreno Maza
2008-03-18