BigO notation and traditional grade school algorithms for addition and multiplication
Bigtheta notation is used in the analysis of an algorithm to give an estimate of runtime complexity and hence a measurement of performance. An algorithm to add two numbers together each having N digits assuming HinduArabic 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 HinduArabic 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 Bigtheta 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…

10^{8} 
10^{7} 
10^{6} 
10^{5} 
10^{4} 
10^{3} 
10^{2} 
10^{1} 
10^{0} 
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 = N^{2}. In the example, if N = 5 then the algorithm runs 25 times. In Bigtheta notation, this relationship can be expressed as Θ(N^{2}).
You must log in to post a comment.