0
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ $\log n-\log \sqrt{n}=\log \sqrt{n}$, if this helps. $\endgroup$
    – zkutch
    Aug 14, 2022 at 17:26
  • 1
    $\begingroup$ 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"? $\endgroup$
    – greybeard
    Aug 14, 2022 at 18:00
  • $\begingroup$ 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. $\endgroup$
    – gnasher729
    Aug 15, 2022 at 7:50
  • $\begingroup$ 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. $\endgroup$
    – Matt Groff
    Aug 16, 2022 at 2:25

1 Answer 1

1
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ what is time complexity of adding $n$ partial sums? My problem arises here... $\endgroup$
    – ali ahmad
    Aug 15, 2022 at 8:12
  • $\begingroup$ Why would it be more than O(n)? $\endgroup$
    – gnasher729
    Aug 15, 2022 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.