How to propose a potential function in amortized analysis?

Question

I have read some posts about amortized analysis, but I still have some question in understanding the potential method.

The major problem lies in how to develop a formal potential function? And how to evaluate the correctness of the potential function?

For instance, there is a question:

A sequence of n operations is performed on a data structure. The ith operation costs i if i is an exact power of 2, and 1 otherwise. Use a potential method to determine the amortized cost per operation.

Adopting potential function, we should first propose a potential function: . Someone tells me that this is very intuitive, but I cannot come up with this even after several hours.....

I find there is a similar question:

need to find the amortized cost of a sequence using the potential function method

However, I think the answer is about the account method.

Answer 1

HINT:

The term k increases every time k increases (obviously), and it increases by 1.

The term 2^ceiling(Lg(k)) increases every time k reaches a new power of 2, and it increases by i/2.