Questions

$ (1)$
Find formulas for a three parts Karatsuba's trick. Using MAPLE or AXIOM, for setting up these formulas, would be a good idea.
$ (2)$
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