respectively then xl , xr , yl , and yr , we also have xl xr and yl yr it follows that xy xl yl (xl yr xr yl ) xr yr notice that this equation consists of four multiplicationsxl yl xl yr xr yl and xr yr which are each half the size of the original problem ( / digitsthe multiplications by and amount to the placing of zeros this and the subsequent additions add only (nadditional work if we perform these four multiplications recursively using this algorithmstopping at an appropriate base casethen we obtain the recurrence ( ( / (nfrom theorem we see that (no( )sounfortunatelywe have not improved the algorithm to achieve subquadratic algorithmwe must use less than four recursive calls the key observation is that xl yr xr yl (xl xr )(yr yl xl yl xr yr thusinstead of using two multiplications to compute the coefficient of we can use one multiplicationplus the result of two multiplications that have already been performed figure shows how only three recursive subproblems need to be solved function value computational complexity xl xr yl yr , , , , given given given given xl xr yr yl - , - , (no(nx yl yr , , , , ( / ( / xl yl xr yr , , , , ( / (nx yr xl yl , , , , , , , , , , , computed above (no(nxl yl xr yr , , , , , (nfigure the divide-and-conquer algorithm in action