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?
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?
As mentioned in exercise 55
Pseudocode for the algorithm
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).
Textbook: Discrete Mathematics and Its Applications
Author: Kenneth Rosen
This full solution covers the following key subjects: Algorithm, Binary, bit, bits, Comparison. This expansive textbook survival guide covers 101 chapters, and 4221 solutions. The full step-by-step solution to problem: 56E from chapter: 4.2 was answered by , our top Math solution expert on 06/21/17, 07:45AM. Discrete Mathematics and Its Applications was written by and is associated to the ISBN: 9780073383095. This textbook survival guide was created for the textbook: Discrete Mathematics and Its Applications, edition: 7. The answer to “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?” is broken down into a number of easy to follow steps, and 26 words. Since the solution to 56E from 4.2 chapter was answered, more than 298 students have viewed the full step-by-step answer.