CITS2200 - Lecture 8

← Back to Home

CITS2200 - Lecture 7
Amortized Analysis - Slides

Introduction to Amortized Analysis

• Amortized analysis evaluates the average cost per operation over a sequence of operations, rather than a single operation in isolation

This is relevant because some operations are usually fast, but have rare occurrences where they are slow

• e.g. appending to a dynamic array:
  • Most inserts are $O(1)$
  • But if the array runs out of space, it takes $O(n)$ time → worst case
    • The entire array needs to be reallocated
• Over many appends, the time complexity of this operation is $O(1)$

Amortized Analysis of Doubling Strategy

• Method of increasing array size by doubling size every time it is full
• Using amortized analysis, the total work is equal to:
  $1+2+...+n=2n$
• This leads to total work being $O(n)$ → efficient method

Amortized Analysis of Multi-delete Stack

• A multi-delete stack has additional operation $-$ $mPop(i):$ delete the top $i$ elements from the stack
• We would think it has time complexity of $O(i)$, but this is not true
  • It is actually $O(1)$ amortized per operation
• Each pop must correspond to a previous push
  • At most $n$ pushes → cost = $O(n)$
  • Total pops $\le$ total pushes $\le$ $n$ → cost = $O(n)$
• Amortized cost per operation:
  $\frac{O(n)}{n}=O(1)$

---

CITS2200 - Lecture 9