CSCE 411 Lecture 14

Lecture Slides

« previous | Wednesday, September 26, 2012 | next »

Amortized Analysis

1. aggregate method: brute force
2. accounting method: assign costs to each operation so it's easy to sum them up while still ensuring the result is accurate
3. potential method: more sophisticated version of the accounting method not covered here

Heap

storing a heap in an array:

100
|-- 19
|   |-- 17
|   |   |-- 2
|   |   `-- 7
|   `-- 3
`-- 36
    |-- 25
    `-- 1

Stored as

a = [ 100, 19, 36, 17, 3, 25, 1, 2, 7 ]

Assume $a$ is indexed from $1$ to $n$ For each array index $i$, $a_i$ has children $a_{2i}$ and $a_{2i+1}$

Adding Element

1. Insert at end of tree (fill bottom row from the left)
2. Compare inserted element with parent. If the added element is greater than parent, swap the two elements.
3. Repeat previous step until added element is comparatively less than its parent or the element is at the root

Adding an element takes $O(\log n)$ (worst-case) time, so adding $n$ elements would take $O(n\log n)$

Removing Element

1. Remove root element
2. Replace root with last element from lowest level
3. Compare new root with children and swap with largest child
4. Repeat previous step until heap property is satisfied.

Removing an element takes $O(\log n)$ (worst-case) time.

Bottom-Up Construction

Place elements in array, interpret as binary tree.

Look at subtrees at height $h$ (measured from lowest level). If these trees have been heapified, then subtrees at height $h+1$ can be heapified by sending their roots down.

Initially, trees at height 0 are all heapified

Analysis

For an array of length $n$, the number of nodes at height $h$ is at most $\lfloor \frac{n}{2^{h+1}}\rfloor$. The cost to heapify a tree at height $h+1$ if all subtrees have been heapified is $O(h)$

$\begin{array}{rl}\sum _{h=0}^{\lceil \log n\rceil }\frac{n}{2^{h+1}}O(h)& \in O\left(n\sum _{h=0}^{\lceil \log n\rceil }\frac{h}{2^h}\right)\\ & \le O\left(n\sum _{h=0}^{\mathrm{\infty }}\frac{h}{2^h}\right)\\ & \in O(n)\end{array}$

Aggregate Method

Show that a sequence of $n$ operations takes $T(n)$ time.

The amortized time is $\frac{T(n)}{n}$.

Example

Pushing an element onto a stack takes $O(1)$ time. Thus pushing $n$ elements takes $O(n)$ time.

Amortized cost per operation is $\frac{O(n)}{n}=O(1)$

Example

Incrementing a binary number: each place has to flip every $2^k$^th increment:

• bit 0 flips with every increment
• bit 1 flips every other increment
• bit 2 flips every 4^th increment
• bit 3 flips every 8^th increment
• bit $k$ flips every $2^k$^th increment

Total number of bit flips in $n$ increment operations is: $\begin{array}{rl}n+\frac{n}{2}+\frac{n}{4}+\dots +\frac{n}{2^k}& =\sum _{k=0}^{\mathrm{\infty }}\frac{n}{2^k}\\ & <n\left(\frac{1}{1-\frac{1}{1}}\right)=2n\\ & \in O(n)\end{array}$

(See MATH 152 Chapter 10.2#Geometric Series→)

Therefore, the amortized time is $\frac{O(n)}{n}=O(1)$.