1.

(a) Give the Karatsuba algorithm for integer multiplication. (b) Derive the recursive formula for analysing its runtime. Give the best possible upper bound on the runtime. (c) Explain why the Karatsuba Multiplication is asymptotically faster than the School Multiplication. (d) Assume that you want to multiply two 10-digit numbers. In terms of runtime, would you prefer the Karatsuba Multiplication or the School Multiplication? Explain vour decision