0

I want to calculate the complexity of multiplying an a-bit number by a b-bit number. Intuitively, this would have complexity $O(ab)$ but I do not know how to show that this is true.

I am also interested in the analogous complexities of division and modular arithmetic in this case so any links to sources such as textbooks or academic papers is greatly appreciated.

Robert S
  • 1,144
  • It is only true when you use the naive method. We have algorithms almost as good as $O(n\log n)$ (recently there is claim that we can do exactly that). – Trebor Apr 04 '19 at 16:13
  • Sorry for not explaining more thoroughly, my question is in relation to the naive implementation of multiplication. However, if you know of any sources that delve into the complexity of the multiplication of numbers of different sizes for other implementations, that would also be of interest to me – Robert S Apr 04 '19 at 16:42
  • https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations – Yuval Filmus Apr 04 '19 at 17:16
  • The above page assumes that the numbers are of comparable size, that is specifically not the analysis that I am looking for. – Robert S Apr 04 '19 at 17:59

1 Answers1

0

You need to perform $ab$ single digit multiplications, and at most $3ab$ single digit additions (just count casually, overcounting anything that is hard to estimate, also, $\min(a,b)$ multi-digit additions). So it's $O(ab)$.

Trebor
  • 4,575