-4
$\begingroup$

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 .

Improve this question
$\endgroup$
3
  • $\begingroup$ Please be more formal in (or elaborate on) addition is asymptotically faster than multiplication. $\endgroup$
    – greybeard
    Apr 1, 2021 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, 2021 at 7:36
  • $\begingroup$ Please do not edit your question to remove its content. Thank you! $\endgroup$
    – D.W. ♦
    Apr 3, 2021 at 21:18

1 Answer 1

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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, 2021 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, 2021 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, 2021 at 17:28

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