Amortised analysis is a method of analysing our algorithm’s performance by averaging the time required to perform a sequence of data structure operations over all operations performed. Even though a single operation might be expensive, we can show that the average cost of an operation will be smaller.
Amortised analysis guarantees the average performance of each operation in the worst case.
There are a few common techniques used in amortised analysis:
In general, in ECE345 — Algorithms and Data Structures, we won’t really use aggregate analysis because it’s a “brute force approach”. Most of the time, we’ll use the accounting method.
slide 7 if cost of operation is less than amount we charge if cost of operation is more than amount we charge
slide 11 cost of 0 is not O(0). it’s O(1)
tutorial 8 notes, exercise 17-2 — on previous exams many times
accounting method: if we have a constant , we must explicitly state what it is (incl in homework)
slide 19 SSSP — single sink shortest path