You saw in class that the standard algorithm to I NCREMENT a binary counter runs

Question

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.

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).

MENT BI0. 0o ,msb) INCREMENT B 0..oo1, msb: while B [i] = 1 B[i] 0 i-i1 RESET BO.. ol, msb): for l 0 to msb B[i] 0 msb 0 ifi>msb

Explanation / Answer

a) O(n)

          this is the time complexity in the worst case

b)O(n)

         this is the worst running time

c)for execution of one operation, there is need of one statement hence it needs O(1)

       the above statements conclude that the amortized time for each operation is O(1)

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

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