# Recurrence relation of multiply two $n$ bit numbers

Suppose given two $$n$$ bits numbers $$A$$ and $$B$$. Also suppose there is a machine that compute multiply two $$\sqrt{n}$$ bits numbers in $$O(1)$$. What is time complexity of multiplying two $$n$$ bits number in a such case?

I think we can use divide and conquer Karatsuba algorithm such that our recursion tree will has height $$\log n-\log \sqrt{n}$$ but at this step I got stuck because the answer is $$O(n)$$.

• $\log n-\log \sqrt{n}=\log \sqrt{n}$, if this helps. Aug 14, 2022 at 17:26
• The problem with Karatsuba&co here: needs $\frac n 2 + k, 0 < k$ bits. Any information about ability to add $2\sqrt n$ bit numbers "plus carry"? Aug 14, 2022 at 18:00
• I would look for a solution to multiply n bit numbers, assuming you can multiply m bit numbers in O(1). I don't think that m = square root of n helps you in any way. Aug 15, 2022 at 7:50
• There is somewhat of a result concerning $O(n)$ time multiplication. You may want to read "How Fast Can We Multiply Large Integers on an Actual Computer?" here: arxiv.org/pdf/1402.1811.pdf It's very readable. Also, you may want to note that multiplication times are usually taken with regards to Turing machines, and today's computers can multiply faster than that, which is in the paper. Aug 16, 2022 at 2:25

If you are asked to find a O(n) algorithm, that is trivial. Split each number in $$n^{1/2}$$ groups of $$n^{1/2}$$ bits, calculate n multiplications in O(n) time, and then add the n partial sums.
Actually, the whole question is a massive abuse of Big-O notation: $$n^{1/2}$$ multiplication is O(1) means there is a constant c depending on the implementation, such that for every large n an $$n^{1/2}$$ multiplication can be performed in time ≤ c. Since n is arbitrary, we can take $$n = n'^2$$ which means two n' bit numbers can be multiplied in O(1). Which means the original problem can be solved in O(1).
• what is time complexity of adding $n$ partial sums? My problem arises here... Aug 15, 2022 at 8:12