Skip to main content
Computer Science

Return to Answer

replaced http://cs.stackexchange.com/ with https://cs.stackexchange.com/
Source Link
Community Bot
Community Bot
  • 1

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?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.

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.

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.

for accounting method
Source Link
hengxin
hengxin
  • 9.6k
  • 3
  • 37
  • 74

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.

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.

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.

Source Link
hengxin
hengxin
  • 9.6k
  • 3
  • 37
  • 74

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.