Big-O notation and traditional grade school algorithms for addition and multiplication

Big-theta notation is used in the analysis of an algorithm to give an estimate of run-time complexity and hence a measurement of performance.  An algorithm to add two numbers together each having N digits assuming Hindu-Arabic positional notation of digits can be written in many ways, two amongst them being; by splitting the digits into base 10 columns and recursively adding each column (grade school method) until only single digits remain or by taking one off the first number and add one to the second number until the first number equals zero (tail recursion).

As we are considering the grade school method, using the example 2 numbers: 47362 and 9388 and assuming Hindu-Arabic positional notation and positive numbers:

Steps

Number 1

Number 2

Make the 2 numbers the same length by introducing zeros at the beginning of the shorter of the two

47362

09388

Count the number of digits (N)

5

5

Starting from the right, add the digits together, carrying a one to the column immediately to the left for every 10 and if carrying is performed, reduce by 10

2 + 8 = 10, carry 1 (-10) = 0

6 + 8 + 1 = 15, carry 1 (-10) = 5

3 + 3 + 1 = 7

7 + 9 = 16, carry 1 (-10) = 6

4 + 0 + 1 = 5

Result 56750

This demonstrates that, in this algorithm, the number of times the algorithm is performed is as a direct result of the value N.  In the example, if N = 5 then the algorithm runs 5 times.  In Big-theta notation we ignore any constants there this algorithm can be expressed as a linear relationship as Θ(N).

Similarly, when we multiply the same sample two N digit numbers:

Starting from the right, multiply the digits (which is carried out by adding a number to itself a given number of times), carrying a one to the column immediately to the left for every 10 and if carrying is performed, reduce by 10 and increase every step by a factor of 10.  Then ad each column…

 

108

107

106

105

104

103

102

101

100

Number 1

4

7

3

6

2

Number 2

0

9

3

8

8

Step 1

3

8 x 4 + 5

 = 7 (c = 3)

8 x 7 + 2

 = 8 (c = 5)

8 x 3 + 4

 = 8 (c = 2)

8 x 6 + 1

 = 9 (c = 4)

8 x 2

 = 6 c = 1)

Step 2

3

8 x 4 + 5

 = 7 (c = 3)

8 x 7 + 2

 = 8 (c = 5)

8 x 3 + 4

 = 8 (c = 2)

8 x 6 + 1

 = 9 (c = 4)

8 x 2

 = 6 c = 1)

0

Step 3

1

3 x 4 + 2

 = 4 (c = 1)

3 x 7 + 1

 = 2 (c = 2)

3 x 3 + 1

 = 0 (c = 1)

3 x 6

 = 8 (c = 1)

3 x 2

 = 6

0

0

Step 4

4

9 x 4 + 6

= 2 (c = 4)

9 x 7 + 3

= 6 (c = 6)

9 x 3 + 5

= 2 (c = 3)

9 x 6 + 1

= 5 (c = 5)

9 x 2

= 8 (c = 1)

0

0

0

Step 5

0 x 4

= 0

0 x 7

= 0

0 x 3

= 0

0 x 6

= 0

0 x 2

= 0

0

0

0

0

Step 6

0

1

1

2

3

2

1

0

0

Total

4

4

4

6

3

4

4

5

6

Step 1 to Step 5 represent the number of times the process runs as a direct result of N = N2.  In the example, if N = 5 then the algorithm runs 25 times.  In Big-theta notation, this relationship can be expressed as Θ(N2).