Question

How many bit operations does the comparison algorithm from Exercise 55 use when the larger of a and b has n bits its binary expansion.

Short answer

Almost n = 2 operations.

We require at most n + 2 comparisons in total.

Step-by-step solution

Step 1

The input of the algorithm is two integers in binary expansion $x=x_1{x}_2\dots x_{n}andy=y_1{y}_2\dots y_m$and

Note that n represents the number of digits of the integers x in binary notation and m represents the number of digits of the integer in y binary notation.

If, $n>m\text{then}x>y$

If, $n<m\text{then}x<y$

Step 2

If $n=m\text{, then}x=y\text{when}{x}_i=y_i\text{for all}i\in \{1,2,\dots ,n\},x<y\text{, when}{x}_i<y_i$$x_i>y_i\text{with}{x}_i,y_i\text{the first set of corresponding digits of}x\text{and}y\text{that differ.}$

We need two comparison to compare n and m (as we need to check $n<m\text{when}n>m$is false) and we need to compare all n digits when m in worst case scenario, which results in n comparisons. Thus we require at most n + 2 comparisons in total.