Prove that at most 2n bits are flipped

Assignment Help Computer Engineering

Reference no: EM132139782

Suppose that we have a binary counter with k bits, where each bit is stored in a array A[0..k - 1]. The operation Increment(A) increments the counter by adding 1 to the content of the counter modulo 2k . The cost of this operation is proportial the number of bits that need to be inspected, so it is at most O(k).

a) Prove that if a sequence of n increment operations is applied to a counter that is initially zero, then at most 2n bits are flipped, by counting the number of bit flips. [Hint: Note that A[0] flips every time, A[1] flips every other time, etc.]

b) Use now the accounting method to prove that at most 2n bits are flipped, when a sequence of n increment operations is executed on a counter that is initially zero.

Reference no: EM132139782

Questions Cloud

Who should claim lead authorship in this scenario : The original research idea is yours, but you let your co-authors handle the data collection and actual writing of the report.

What proportion of participants fell in category : Participants who score between 26 and 30 on this scale are categorized as overweight. What proportion of participants fell in this category?

What would the future and present value : What would the future and present value be if above annuity were an annuity due? (Do not forget to switch your calculator to BGN mode)

What kind of sampling method is being used : Ten 1st grade classrooms are randomly selected from across the county. What kind of sampling method is being used?

Prove that at most 2n bits are flipped : The cost of this operation is proportial the number of bits that need to be inspected, so it is at most O(k).

What is the probability that robins made : Assuming these data are normally distributed, what is the probability that robins made more than 11 birdcalls during this experimental session?

What might be the shortcomings of your method : Suppose that you have a database of three-dimensional galaxy coordinates x; y; z that covered a large volume of, say, 3 Gpc 3 Gpc 3 Gpc.

Evaluate sensitivity analysis for different financial models : Analyze and evaluate sensitivity analysis for different financial models, including the Yield Curve and its usefulness in predicting recessions

Calculate the total number of memory bytes present : Suppose that the BCR stores only one bit value. Calculate the total number of memory bytes present in the system.

User Account

All Pages