Answer to Question #99244 in Algorithms for Bob

Question

Squaring a binary number requires a number of
additions (of binary digits) - as well as other manipulations such as
copying strings of bits and layout. Assuming an addition counts as
one operation and other manipulations don't count as operations
then calculate a worst case scenario value for the Big-O of the
squaring function assuming the values being squared have N binary
digits - i.e. Squaring = O(f(N)). Approximate f(N).

Answer 1

The binary number has $n$ digits. Squaring it would require multiplying the entire number by 0 or 1, copying this result alongside adding appropriate number of zeroes at the end, and finally adding all these results to obtain the square of the binary number.

Now, the number of times this copying operation is done is equal to the number of digits in the binary number, which is $n$ here.

Basically, square is obtained as the sum of :

$n-bit$

$n+1-bit$

$n+2-bit$

.

.

.

$n+n-1-bit$

Summing all these numbers gives us the result.

Now, summing n digits (as there are n rows of digits) in binary gives rise to a $O(n)$ time complexity.

Also, there are n such columns of n digits each, thus making the time complexity as $O(n*n)=O(n^2)$ .

Now, the number of digits in each column after these n columns (of n digits each) from the left, decrease by 1 successively, which means $(n+1)^{th}$ column from the left consists of $(n-1)$ digits and so on, till the rightmost column ( which contains 1 digit only).

Thus, time complexity for addition of this block of digits require :

$O(1+2+...+(n-1))=O(n*(n-1)/2)$

$\implies O((n^2-n)/2)$

Thus, the total time complexity for the squaring operation becomes :

$O(n^2+[(n^2-n)/2])=O((3n^2/2)-(n/2))$

Moreover for large values of n ,

$O(n^2)>>>O(n)$

Thus we can neglect the $O(n)$ term.

Hence time complexity is $O(n^2)$ (as constants are neglected in order).