Use big-theta 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:22 pm ad1c9bdddf
To add two n digits numbers, we will need to perform
- minimum n individual additions, one at each digit position, when no carry results from any addition.
- maximum (2n - 1) ...
Solution assumes familiarity with big-theta notation, and gives a brief explanation, more like a guidance to student.