Explore BrainMass

Analyzing the complexity of addition and multiplication

This content was COPIED from BrainMass.com - View the original, and get the already-completed solution here!

Use big-O notation to classify the traditional grade school algorithms for addition and multiplication. That is, if asked to add two numbers each having N digits, how many individual additions must be performed? If asked to multiply two N-digit numbers, how many individual multiplications are required?

© BrainMass Inc. brainmass.com March 21, 2019, 7:16 pm ad1c9bdddf

Solution Preview

The algorithm for addition is as follows: For each digit, from right to left, add the digit to the corresponding digit in the other number. Apply the "carry" if needed. There is one addition operation per digit. So the complexity, in big-O notation, is O(n).

Example: Consider adding 123 ...

Solution Summary

This solution provides a detailed analysis of the basic addition and multiplication algorithms that grade school students learn.