We just started learning the potential method this week and I'm having a bit of trouble on this problem regarding Fibonacci numbers; specifically I'm having some difficulty thinking of a good potential function.
Suppose instead of powers of two, we represent integers as the sum of Fibonacci numbers. In other words, instead of an array of bits, we keep an array of fits, where the $i$th least significant fit indicates whether the sum includes the $i$th Fibonacci number $F_i$. For example, the fitstring 101110 represents the number F6 + F4 + F3 + F2 = 8 + 3 + 2 + 1 = 14.
a. Describe an algorithm for an increment operation.
b. Show that a sequence of $n$ operations is amortized $O(n)$ using the potential method.
c. Do the same thing above, but now add a decrement operation.
This is what I started out with:
The general rule is to never let two consecutive Fibonacci numbers exist in the counter at the same time. In other words, no two 1's can occur consecutively. This is because of the definition of Fibonnaci numbers, i.e. a number such as 011 can be replaced by 100.
In general, when incrementing, change the least significant bit that's a 0 to 1 (this is one of the two "1" representations that are the first two bits in the counter). Starting from the most significant bit, if some positions $i$ and $i-1$ have 1's, then change them to 0's and change position $i+1$ to a 1. Keep recursing until there are no more consecutive 1's.
Now we will use the potential method to show that the amortized cost of $n$ consecutive increment operations is $O(n)$.
We will define our potential method as follow: (this is one part I'm having trouble with)
I then made the following observation: Suppose the $i-th$ operation makes $x_i$ Fibonnaci conversions (changing consecutive 1's to 0's and changing the next significant bit to a 1). Then the actual cost is $1 + 3x_i$.
Any help is appreciated! Thanks!