Goal: prove that insertion is O(1) amortized even though it is O(log n) in the worst case 39:26, 38:28.

Identifying the actual cost

  • Elicited from the class: the real cost of an insertion is governed by the number of trees already in the forest, since each merge destroys one tree 40:49, 41:19, 41:40.
  • Writing t for the old number of trees and t' for the new number: actual cost of insert = O(t − t' + 1) 41:40, 42:15.

The potential function

Φ(state) = number of trees in the forest

42:15

Insert: amortized O(1)

amortized = actual + ΔΦ
          = (t − t' + 1) + (t' − t)
          = 1

The t terms cancel exactly, leaving a constant 42:58, 43:23.

Note on the O(·): hiding a constant c in the actual cost just means putting the same c in front of the potential term; it does not affect the conclusion 42:58.

The other operations

  • The actual cost of delete-min and decrease-key is at most log n 43:23, 43:57.
  • The potential difference is bounded too, because the forest never holds more than log n trees 43:57.
  • So the same calculation rebounds the other operations at O(log n) amortized 43:57.