Search code examples
algorithmanalysis

Prove or disprove: it is asymptotically faster to square an n-bit integer than to multiply two n-bit integers

Prove or disprove: it is asymptotically faster to square an n-bit integer than to multiply two n-bit integers.

Solution

  • If x and y are two n bit numbers, then x+y is an n+1 bit number. ((x+y)^2 - x^2 - y^2)/2 is xy.

    So multiplication of two n bit numbers is at most as expensive as 1 addition, three squarings, two subtractions, and a divide by 2.

    Since addition, subtraction and division by 2 are Theta(n), this shows that squaring can't be asymptotically faster.