# Sequence of N operations Amortized Analysis

A sequence of $N$ operations is performed on a certain data structure.

The $i$-th operation costs $i$ if $i$ is a power of 2, else it costs 1.

How can I calculate the amortized cost for every operation using the potential function method?

• What have you tried? Where did you get stuck? We want to help you with your specific problems, not just do your (home-)work. However, as it is we don't know what this problem is and thus how to help. See here for a relevant discussion. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? – D.W. May 19 '14 at 6:18

How about this. Assume we maintain a binary counter $C$ that counts the operations executed so far. Let $D_i$ be the data structure after the $i$-th operation. We then define as potential $\Phi(D_i)$ number of $\tt 1$-digits in $C$. As usual $c_i$ denotes the actual costs, and $\hat c_i$ the amortized costs.

If $i$ is not a power of two, then we have $$\hat c_i = c_i + \Phi(D_i) - \Phi(D_{i-1}) \le 2 .$$ This is true since the addition of a $\tt 1$ on $C$ will turn one digit from $\tt 0$ to $\tt 1$ while possibly turning some digits from $\tt 1$ to $0$.

If $i$ is a power of two then clearly $$\hat c_i = c_i + \Phi(D_i) - \Phi(D_{i-1})= i + 1 - (i-1) =2 .$$

As a final comment, the amortized costs do always depend on the potential function. So another potential function yields different amortized costs.

• To avoid confusion, can we rewrite it as $\hat c_i = c_i + \Phi(D_i) - \Phi(D_{i-1})= 1 + i - (i-1) =2$ – Mojo Jojo Sep 5 '16 at 12:46

I don't know about the potential function method, but to calculate the amortized cost, you compute the total cost of $n$ operations and divide by $n$. In this case, if we denote by $x_i$ the cost of the $i$th operation then $$\sum_{i=1}^n x_i = n + \sum_{2^j \leq n} (2^j-1) \leq 3n,$$ and we can conclude that the amortized time $O(1)$. I'll let you carry out the calculation and detail, and figure out how to apply the potential function method.

• Note: Your solution is the counting method for amortized analysis. The question asked explicitly for the potential function method. – NightRa May 18 '14 at 9:38
• @NightRa I find it somewhat idiotic that a question asks for such a particular proof method. In "real life" you calculate the amortized complexity in whatever which way is the most appropriate. – Yuval Filmus May 18 '14 at 13:53
• When learning about a topic it is a good way of practicing to work out how a complicated methods works on a simple problem. – Kaveh May 21 '14 at 0:30