algorithm design techniques it is easy to see that now the recurrence equation satisfies ( ( / (nand so we obtain (no(nlog ( to complete the algorithmwe must have base casewhich can be solved without recursion when both numbers are one-digitwe can do the multiplication by table lookup if one number has zero digitsthen we return zero in practiceif we were to use this algorithmwe would choose the base case to be that which is most convenient for the machine although this algorithm has better asymptotic performance than the standard quadratic algorithmit is rarely usedbecause for small the overhead is significantand for larger there are even better algorithms these algorithms also make extensive use of divide and conquer matrix multiplication fundamental numerical problem is the multiplication of two matrices figure gives simple ( algorithm to compute abwhere aband are matrices the algorithm follows directly from the definition of matrix multiplication to compute ci, we compute the dot product of the ith row in with the jth column in as usualarrays begin at index /*standard matrix multiplication arrays start at assumes and are square *matrix operator*const matrix aconst matrix int numrows)matrix cnn }forint ++ /initialization forint ++ ci ] forint ++ forint ++ forint ++ ci ] +ai ] bk ] ]return cfigure simple ( matrix multiplication