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?
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.
Can you please provide the slides?
the slides are the second half of the following: github.com/kbuchin/slide-archive/blob/main/advanced-algorithms-2024/02-Amortized-Analysis.pdf
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?
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.
Heyy, thanks for this! Great work!
you are a legend!
thank u so much
This is fantastic
Thanks!