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: 
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.
Consider the steps the computer needs to take in order to accomplish these tasks. Remember that computers work drastically different from people.