1 Amortized Analysis

• consider the sequence of operations $o_1,o_2,o_3 ...$
• consider the worst case, without probability involved

1.1 aggregate analysis

• T: worst-case time
• take amortized cost as ${\sum_n T(o_i)} \over {n}$

1.2 accounting method

• overcharges some operations early in the sequence, storing the overcharge as “prepaid credit” on specific objects in the data structure. Later in the sequence, the credit pays for operations that are charged less than they actually cost.
• any ops seq: (amortized) $\sum \hat{c_i} \ge \sum c_i$ (actual)

1.3 potential method

• maintain a sum of credit in stead of “storing them somewhere”
• associate the potential with the data structure as a whole rather than with specific objects within the data structure.
• $\hat{c_i}=c_i+\phi(D_i)-\phi(D_{i-1})$
• $\sum \hat{c_i}=\sum c_i+\phi(D_n)-\phi(D_0)$, with $\forall i, \phi(D_i) \ge \phi(D_0)$
• potential may be used to give lowerbound: $(\phi_{final}-\phi_{init})/|max \ \Delta \phi|$

e.g. (A) Splay Tree

space efficient

original paper

see hand-written notes

e.g. (B) Disjoint Sets with Union(DSU)

• n elements, n sets at the beginning
• merge(x,y): merge two elements’ set
• query(x,y): if they’re in the same set
• to simplify analysis, n=max(n, # of operations)

approach 1: Reps

• rep(x) = representative of the set containing element x
• set(x) = the set of all elements represented by x
• O(n) for merge to change rep, O(1) for query

approach 2: Graph

• consider element as vertex in a graph
• O(1) for merge/link to build an edge, O(n+m) for query, where m is the number of edges

approach 2.1: Tree

• try to make the graph sparse by keep each connected component as a tree
• rep(x)=root
• merge(x,y) ↔ link(rt1,rt2), query(x) ↔ find_root(x)
• if merge=query+link
  • O(n) for merge, O(n) for query, O(1) for link

observation: if always merge small set into large one

• keep track of the set(x)
• amortized analysis!
• approach 1.2:
  • O(log(n)) for amortized merge: for each element, its rep can be changed at most log(n) times
  • O(1) for amortized query
• approach 2.2:
  • O(1) for amortized link
  • O(log(n)) for amortized find_root: for each node, its root can be changed at most log(n) times

link by rank(x) instead of size(x)

• no need to do amortized analysis
• rank start with 0
• merge smaller rank into larger one but don’t change their rank
• if of the same rank, just pick one of them as father and increment the father’s rank by 1
• reduction: rank k → size of subtree is 2^k
• outcome: rank along a path from leaf to root must be increasing

approach 1.2+2.2+path compression

• when we find_root, we can actually update information for all ancestors
• use tree, but also store the rep/father; change it each time we could
• when a node’s rank increased from k-1 to k as a root, we’re sure that it has a subtree of size 2^k; look at all n elements among the whole time, all these subtrees are disjoint
• so there’re at most n/(2^k) elements have a rank k
• if rank is at least r: $n/2^r+n/2^{r+1} .... \le 2n/2^{r}$

log*

$$ \log^(n)=1+\log^(\log n), \log^* (0\ or\ 1)=0 $$

• group nodes by their log(rank)*
• edge tranversed = E1(x.parent=root) + E2(x&x.parent are in different group) + E3(.. in the same group)
• E1 → the last edge → O(1) *n
• E2 → # of group → O(log*(n)) *n
• E3 → ranks in group i rangeing $[i,2^i)$
• consider future: # of future parents of x in group i is at most 2^i because of strictly increasing rank

$$ |E_3| \le \sum_{group_i} \sum_x 2^i \le \sum_{group_i} 2^i * 2n/2^i = O(n \log^* n) $$

e.g. (C) Heap

Heap

• Binary Heap: node k with children 2k and 2k+1
• property of max heap: value at k is larger than or the same with values at its children
• push: put a node at leaf and swap up until the property is satisfied
• pop_max: swap with a leaf, and swap down with its larger child until the property is satisfied
• height of tree: obviously O(log n)
• can’t be faster for a sequence of operation, otherwise we can have sorting with comparison faster than nlogn with push and then popmax

what if a sequence of n push operations?

• two strategy: bubble up or bubble down
• bubble down: $\sum 2^i * (K-i)=\sum 2^{K-i} * i = O(2^k) =O(n)$

Binomial Heap

Binomial Tree: $T_n=T_{n-1}.root <-> T_{n-1}.root$

Binomial Heap

• a sequence of binomial trees of distinct degree (if same, merge)
• each satisfies heap property
• similar to binary number
• therefore n pushes → binary counter
• amortized time: push O(1), pop_max O(logn), increase_key O(logn)
  • using accounting method is easy to understand
• if pop is not very many, faster than binary heap
• still, not possible to decrease pop_max anymore given the sorting bound

Fibonacci Heaps

• degree is defined by the degree of the root
• a sequence of trees of distinct degree (if same, merge)
• be lazy about the degree distinction property
• increase_key: if heap property broken, just disconnect with its parent, O(1) [where faster]
• push: just a new single node, O(1)
• pop_max: clean up by merging trees with the same degree

pf.

• what if a tree with many children such that popping it results in many merge
• motivation: let degree large
• marking rule: if x lose its children for twice, disconnect with its parent to become root at its own
• potential method

$$ \phi=|roots|+2|marked| \\ push: O(1) \\ increase\_key: \\ pop\_max: $$

if no increase_key: deg(v0)=0, deg(v1)=1, deg(v2)=2, deg(v3)=3, deg(v4)=4, deg(v5)=5