Problem 56E

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

Solution

In this question we have to find the number of bit operations used by the comparison algorithm

when the larger of a and b has n bits in its binary expansion?

Step 1

As mentioned in exercise 55

Pseudocode for the algorithm

procedure compare

while

if then print “a is less than b”

if then print “a is equal to b”

if then print “a is greater than b”.

For every j there is one bit comparison since in the worst condition there can be total n bit operations .

Therefore we can say that there will be at most n bit operations.

Thus the Complexity is O(n).