Time complexity of multiplication of numbers of different size

277 Views Asked by At

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.

1

There are 1 best solutions below

0
On

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)$.