資料結構與演算法

(5 points) Consider the task of incrementing a $k$-bit binary counter from all zeroes to all ones. Let $A$ be an array of length $k$ that simulates the counter, where $A[0]$ represents the least significant bit and $A[k-1]$ represents the most significant bit. We implement the INCREMENT() operation as follows:

function INCREMENT()
    i = 0
    while A[i] == 1 do
        A[i] = 0
        i = i + 1
    A[i] = 1

Unfortunately, this counter is implemented on a deficient random access memory machine (RAM). On this machine, each read-access to a single array entry takes 1 unit of time. However, a write to an entry may take different amount of time. In particular, for any index $i$ ($0 \le i < k$), if $i$ is a multiple of 3 but not a multiple of 5, the memory stick will fizz and it will take exactly $3^{i/3}$ units of time to write the data into $A[i]$. If $i$ is a multiple of 5 but not a multiple of 3, the memory stick will buzz and it will take exactly $5^{i/5}$ units of time to write the data into $A[i]$. Writing into all other entries not mentioned above takes 1 unit of time as usual.

Please design a potential function $\Phi(A)$ such that the amortized time (using $\Phi(A)$) per INCREMENT() operation is still $O(1)$ when incrementing from zero. Make sure your potential function is rigorously defined, can be evaluated into an actual number by human beings, and as clean and efficient without ambiguity. For example, if you left any undetermined variable (such as "for some constant $c$") in your expression, you must state an actual number for that variable (e.g., "$c = 1$"). You do not need to verify your answer in the answer sheet. This problem has no partial score.