Skip to main content
3 of 3
replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/

The method of $O(f(n))/n$ is often called the aggregate analysis. It is useful when we are clear about the operation sequence. The dynamic array and binary counter are typical examples of this kind.

However, sometimes (maybe usually) we don't know the operation sequence and are not able to obtain the $O(f(n))$. Then we need other techniques such as accounting method or potential method.

For the accounting method, you can refer to this post: How can I make sense of amortized accounting method?.

I am not quite familiar with the potential method. It is more sophisticated. Waiting for other answers about it.

hengxin
  • 9.6k
  • 3
  • 37
  • 74