Next: Divide-and-conquer multiplication. Up: Multiplying. Previous: None.

Grade-school multiplying

You probably learned to multiply multi-digit numbers in grade school. This technique didn't involve any recursion.

     2412
   x 3231
---------
     2412
    7236
   4824
+ 7236
---------
  7793172

Analyzing this algorithm using big-O analysis proceeds in two steps, just like the algorithm. First, we look at the amount of time it takes to write the n numbers below the line. Each number takes O(n) time to compute, and there are n numbers, for a total of O(n²) time for this first phase.

The second phase is the addition phase. For this phase, we go through each of the 2n columns, totalling the up to n digits within the column (plus an additional number obtained from the carry of the previous column). Each column takes O(n) time, and so the overall time for this phase is O(n²).

The total time for both phases of the grade-school algorithm, therefore, is O(n²) + O(n²) = O(n²).

Next: Divide-and-conquer multiplication. Up: Multiplying. Previous: None.