3. You saw in class that the standard algorithm to INCREMENT a binary counter ru

Question

3. You saw in class that the standard algorithm to INCREMENT a binary counter runs in O(1) amortized time. Now suppose we also want to support a second function called RESET, which resets all bits in the counter to zero.

Here are the INCREMENT and RESET algorithms. In addition to the array B[. . . ] of bits, we now also maintain the index of the most significant bit, in an integer variable msb.

INCREMENT(B[0 .. ], msb): i0

while B[i] = 1 B[i]0 ii+1

B[i]1 if i > msb

msb i

RESET(B[0 .. ], msb): for i 0 to msb

B[i]0 msb0

In parts (a) and (b), let n denote the number currently stored in the counter.

(a) What is the worst-case running time of INCREMENT, as a function of n?

(b) What is the worst-case running time of RESET, as a function of n?

(c) Prove that in an arbitrary intermixed sequence of INCREMENT and RESET operations, the amortized time for each operation is O(1).

Explanation / Answer

Answer for question:

Part a:

The worst case running time of increment worst case running time is O(1)
but it has traverse up to msb check.so it will iterate the over the B array.
So every time each operation will take O(1) time for n times it will take O(n) times.

Part b:

I similar to Increment function
The worst case running time of reset worst case running time is O(1)
but it has traverse up to msb check.so it will iterate the over the B array.
So every time each operation will take O(1) time for n times it will take O(n) times.

Part c:

See the below arbitrary mixed sequence of Increment and Reset
Operations of each iterate will take O(1) time.

INCREMENT_RESET(B[0 .. ], msb): i0
while B[i] = 1 B[i]0 ii+1
B[i]1 if i > msb
msb i
for i 0 to msb
B[i]0 msb0

So if we observe that each operation of Increment or reset will take O(1) time.

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.