complexity-theory - O(1) の償却時間がかかる操作は、最悪の場合 O(n^2) 時間になる可能性がありますか?

Question

操作の償却時間が O(1) の場合、最悪の場合、O(N^2) 時間かかることがありますか?

Answer 1

Yes, it can. Amortized complexity takes into account the frequency with which the worst case appears. Thus as soon as the worst case appears in about 1 in N^2 operations the amortized complexity will be constant.

Let's take a simple example - the dynamically expanding array(I will call that vector as it is called in c++) in most languages has an amortized constant time for pushing an element to its back. Most of the time pushing an element is a simple assignment of a value, but once in a while all the elements allocated will be assigned and we need to re-allocate the vector. This would be the worst case of a push_back operation and when that happens the operation is with linear complexity. Still the way vector grows makes sure that re-allocation is infrequent enough. Each time the vector is re-allocated it doubles its size. Thus before another re-allocation happens we will have n simple push_back operations(assuming n was the capacity of the vector before re-allocation). As a result the worst case of linear complexity appears at most once in a linear number of operations.

Analogously to the case above imagine a data structure that re-allocates in O(n^2), but makes sure that re-allocation is performed at most once in n^2 constant operations. This would be an example of an operation with amortized complexity of O(1) and worst-case complexity O(N^2).