Squaring n-bit int vs. multiplying two n-bit ints

Question

Disclaimer: Homework question. I'm looking for a hint…

Professor F. Lake tells his class that it is asymptotically faster to square an n-bit integer than to multiply two n-bit integers. Should they believe him?

I believe that multiplying two n-bit ints via shift/add is an O(n) operation, but I can't see why squaring an n-bit int would be any different. Am I missing something?

Answer 1

Since you wanted only a hint, answer comes from this equation: (a + b)^2 = a^2 + b^2 + 2*a*b

To not spoil the puzzle, I've posted complete solution separately :)

Answer 2

Imagine that squaring is actually asymptotically faster. Then if you have a * b, you could calculate:

a = m + n
b = m - n

Then solving this equation system gives:

m = (a+b)/2
n = (a-b)/2

But then we have

a * b = (m+n)*(m-n) = m² - n²

or without intermediate variables:

a * b = ((a+b)² - (a-b)²)/4

So you can replace any multiplication by two squaring operations (and some additions and division by 4, which is just a bit shift, and these can be all ignored for asymptotical complexity). So the complexity of multiplication is at most twice the complexity of squaring. Of course, "twice" is a constant factor, which means both have the same asymptotical complexity.