CODEWITHSUNDEEP
time-complexity
Shiu Chun Ming
Shiu Chun Ming

Reputation: 227

Time complexity of multiplication by repeated addition

Here is an example about analyzing the time complexity of different multiplication algorithm from my textbook:

If we do multiplication by repeated addition:

4 * 7 = 7 + 7 + 7 + 7

The time complexity would be O(n*10^n), where n is the digit.

I don't feel good about analyzing time complexity when n is digit. Could anyone explain to me why it is O(n*10^n)?

Upvotes: 2

Views: 950

Answers (1)

clemens
clemens

Reputation: 17722

A number N has O(log N) digits, where log denotes the decimal logarithm. The addition of N with itself therefore requires O(log N) steps, and doing that M times requires O(M log N) steps. For M in O(N) you get O(N log N) steps. This estimate is based on the numbers. If you want the number of digits n as base, you must substitute N with 10^n, which gives O(n 10^n).

Upvotes: 4

Related Questions