--- technical details ---

CLRS (3rd edition) defines three types of amortized cost analysis. The first type ("aggregate analysis") requires us to show that for all sequences of n operations, the total actual cost of performing those operations in that sequence is less than some function T(n). We can then say that the amortized cost of all such operations is T(n) / n. This makes it necessary that cheap operations precede expensive ones.

The second type ("the accounting method") is different: we assign potentially-inaccurate prices to all operations. These prices will be constant regardless of the actual cost of performing those operations. Conceptually, an operation is in "credit" if its actual cost is less than its assigned price, and it is in a state of owing if its actual cost is more than its assigned price.

We must then assign prices that make it possible to show that, for all sequences of operations, the total actual cost of all operations from the start of the sequence to point n within it is less than the total amortized price assigned by our price schedule. (Stated another way, while an individual operation is free to "owe", a sequence of operations may never be in an "owing" state.) If we can prove that, we are justified in making a claim about the amortized cost of the operations we considered. (Under this method, the amortized cost of an operation is equal to the price we assigned it.) This also makes it necessary that cheap operations precede expensive ones.

The third type ("the potential method") defines a potential function which evaluates the state of the data structures maintained by the algorithm. ("Potential" in the sense of potential energy, which can be stored and later released.) It then says that the amortized cost of an operation is equal to the actual cost, plus the difference in "potential state" caused by the operation. Conceptually, if potential is raised, the amortized cost was higher than the actual cost (and has built up a buffer that later operations may draw down), and if it is lowered, the amortized cost was lower than the actual cost.

As before, we must show that no sequence of operations can place the data structure into a state of negative potential. Cheap operations must precede expensive ones.

------

Now, why was pyon telling you you should be ashamed of your post? It's almost certainly these two paragraphs:

>> If you read more about big-O, you may see the word “amortized” thrown around. That’s a fancy word for “average,” meaning that individual occurrences don’t all behave exactly the same, but over the long run, averaging over many operations, the behavior has a certain characteristic.

>> The analysis we’ve been doing is for the average behavior. Lots of operations can behave much worse in unusual circumstances. Adding a key in a dict and looking up a key are O(1), which is true for typical data. But if you understand the internals of dicts, you can carefully craft a set of keys that will perform terribly, with O(N) behavior. Filling that dict would take O(N²) time.

Your post has confused average-case analysis with amortized analysis. (And it makes this problem worse by implying that the two terms refer to the same concept.) The point of amortized analysis is that you cannot see worse performance than the amortized cost.

An amortized analysis is deterministic and averages runtime costs over the different operations that are present in a sequence of operations beginning from a given initial state; an average-case analysis is stochastic and averages runtime costs of a single operation over many different performances of that operation against different initial states. These two terms are not synonymous and they don't belong to the same universe of terminology; if we're thinking about "average-case analysis", then an amortized analysis is a type of "worst-case analysis", not a type of average-case analysis.

The first paragraph I quoted tells us that you're talking about amortized analysis, but you aren't: the example you provide is of an average-case analysis. If the amortized cost of adding a key to a dictionary were O(1), it would be impossible for adding a sequence of N keys to that dictionary to take more than O(N) time. (As is in fact the case for the Python list.append example you mention beforehand.)