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: 
Here's [a hint](http://en.wikipedia.org/wiki/Multiplication_algorithm#Linear_time_multiplication). 

And here's my solution in SECRET CODE:Fdhnevat zrnaf lbh bayl unir gb qb bar vavgvny SG, abg gjb, fb vg'f snfgre.
Consider the steps the computer needs to take in order to accomplish these tasks. Remember that computers work drastically different from people.