The Algorithm Design Manual (3rd) Exercise Solution 'E2-42'

Table of Contents

Introduction
Repository
Exercise 2-42
- Question
- Solution

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 2-42

Question

When you first learned to multiply numbers, you were told that $x ×y$ means adding x a total of y times, so $5 × 4 = 5 + 5 + 5 + 5 = 20$ . What is the time complexity of multiplying two n-digit numbers in base b (people work in base 10, of course, while computers work in base 2) using the repeated addition method, as a function of n and b. Assume that single-digit by single-digit addition or multiplication takes $O(1)$ time. (Hint: how big can y be as a function of n and b?)

Solution

[1] Name the two n-digit numbers as x, y.

x's replesentation in terms of n and b is following (the same applies y).

\begin{equation} b^n \le x \lt b^{n+1} \end{equation}

So, the time complexity we want is multiple of the time complexity required for the calculation of " $x+x$ " and $O(b^n)$ .

[2] When we calculate " $x+x$ ", single-digit additions are required per its digits.
x has n digit, so the time complexity for this calculation is $O(n)$ .

[3] From [1] and [2], the time complexity we want is:

\begin{equation} T=O(n)*O(b^n)=O(nb^n) \end{equation}