For this time, we need toimplement an amortized-analysis classic, the Binary Counter. You will count the number of steps actually executed in the algorithm to see if the bound given by amortized analysis is accurate.

Binary counter Pseudocode

Increment(A, k)

i = 0

while i < k and A[i] = 1

A[i] = 0

i = i + 1

if i < k

A[i] = 1

The Binary Counter algorithm increments a k-bit binary counter that counts up from from 0. We use an array A[0..k-1], with lower-order bits on the left and higher-order bits on the right.

In a traditional analysis, we would say that a single execution of Increment takes O(k) time in the worst-case, and therefore a sequence of n operations would take O(nk) time. In our discussion of aggregate analysis, we said that cost of n operations is O(n), yielding an amortized cost of O(1) per operation.

We will keep k = 64 constant for all experiments, but vary the value of n, the number of times Increment is called.

Your program will:

Implement the Increment subroutine given below.

Modify the Increment subroutine so that it counts the number of steps executed in each call.

We focused our analysis in class on the number of bits flipped, and our job today is to see how accurate we really were. When counting the number of steps increment your counter for any line of code you would count as O(1) or more in traditional analysis.

Write a driver that initializes an array of size k with all zeroes, and then calls the Increment subroutine n times (try n = 256, 512, and 1024 for starters).

Your driver should count the total number of steps returned by Increment, and sum this result over all calls.

Now for your conclusion: Do your results support the amortization result that n operations yields an amortized cost of O(1)? Put an answer to this question in a comment at the top of your code, with justification. If youre not confident in your answer, try varying k as well as n.

Numbers for The Bound

Keep k = 64 and vary n. The traditional analysis tells us that n operations takes O(nk) time, but amortized analysis gives us O(n) steps for n operations.

k = 64, n = 256.

k = 64, n = 512.

k = 64, n = 1024.