Let $T_1(n)$ be the time complexity of computing the square of an $n$-bit integer, and let $T_2(n)$ be the time complexity of computing the product of two $n$-bit integers.

Assuming that addition is asymptotically faster than multiplication, which of the following is correct?

  1. $T_1(n) = \Theta(T_2(n))$.
  2. $T_1(n) = o(T_2(n))$.
  3. $T_2(n) = o(T_1(n))$.

Please choose one correct option of above .

  • $\begingroup$ Please be more formal in (or elaborate on) addition is asymptotically faster than multiplication. $\endgroup$ – greybeard Apr 1 at 17:35
  • $\begingroup$ So you will live with answers implying ignoring constant factors used in CS more than not. Which is entirely in line with big-O and Little-o relations. $\endgroup$ – greybeard Apr 3 at 7:36
  • $\begingroup$ Please do not edit your question to remove its content. Thank you! $\endgroup$ – D.W. Apr 3 at 21:18

Observe that $ab=\frac{1}{2}\left((a+b)^2-a^2-b^2\right)$,

hence multiplication requires three squaring operations and 3 additions/subtractions (division by 2 is easy), which means squaring is asymptotically as hard as multiplying.

  • $\begingroup$ This shows me that you do not really understand the definitions. What does it mean for $T_1$ to be the complexity of squaring? Can you tell why $T_1,T_2$ are both $\Omega(n)$? Can you tell that $T_1=O(T_2)$? $\endgroup$ – Ariel Apr 1 at 10:21
  • 2
    $\begingroup$ This shows clearly “squaring can’t be much easier than multiplication, because we can multiply using three squaring operations, so multiplying takes at most three times as long”. It should be obvious that squaring isn’t harder than multiplying (because x squared = x times x), so this provides the answer. $\endgroup$ – gnasher729 Apr 1 at 14:39
  • 1
    $\begingroup$ @anirudh. The answer to your question follows immediately from what's written in this answer. Please put some effort in trying to understand it and learning the material. $\endgroup$ – Steven Apr 1 at 17:28

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