Potential method for amortized analysis

I give an introduction to the potential method by the example of a multi-pop stack and a binary counter.
I recommend to watch my previous video introducing amortized analysis with aggregate analysis and the accounting method first: • Amortized Analysis: Ag...
I start this video by re-introducing the multi-pop stack and its amortized analysis using the accounting method. If you just watched my other video start at 07:00.
00:00 Introduction
00:45 multi-pop stack
02:56 accounting method: multi-pop stack
07:00 from accounting to potential
09:30 potential method
12:27 potential method: multi-pop stack
16:08 Why Phi(D_n) larger equal Phi(D_0)?
19:05 binary counter
22:00 potential method: binary counter

[@telan3467]

This is fantastic

[@vsvg3]

Heyy, thanks for this! Great work!

[@gawadahmed3722]

you are a legend!

[@user-uy1sl4sk3f]

Thanks!

[@kimjaeyoon366]

thank u so much

[@user-uy1sl4sk3f]

Could you please give me an idea, how the base-3 counter amortized cost will be calculated here?
I am getting, Ci = 2, Potential change = 2. So, amortized cost = 4. Is it okay?

[@algorithmslab]

This doesn't quite work, because Ci might not be constant.
The first question you need to do is to define an appropriate potential function. For the binary counter it was the number of 1s, but here it has to look different (Hint: It has to involve the number of 2s. It can also involve the number of 1s.) c_i is the actual cost. Just like for the binary counter, this may vary, i.e., it is not necessarily constant. The trick then is (again like for the binary counter) to make sure to have defined the potential function in such a way, that whenever the counter has to change many digits, that then the potential drops by a similar number. This is a nice exercise.

[@GiorgiChapidze-dy2iw]

Hi!
So when number is 2^n - 1 number then it will have 2 ^ n flips. For 3 : 3 flips, for 2^3 -1 =7 : 4 flips. For 2 ^ n - 1 number n + 1 flips.
Because c = 1 and from 2 to 3 in binary representation as from n-1 to n potential is 1, we get 1 + 1 = 2 and c^ is 2. Did I understand it correctly?
Thanks!

[@algorithmslab]

Yes, I think so. When we go from 2^n - 1 to 2^n then we have n+1 flips. (In the first sentence you mention 2 ^ n flips; this might be a typo, but your third sentence states this clearly.). And yes, when we go from 2 to 3, then c=1 (1 flip) and the potential goes up by 1 (from 1 to 2), thus the amortized cost is 2.

[@GiorgiChapidze-dy2iw]

@@algorithmslab Thank you :)