Data-structures 2

Amortized complexity #definition

\begin{matrix} Method of assessing algorithms performance based on it over-all complexity, \\ and not just worst edge-cases \end{matrix}

\begin{matrix} Compute total cost over multiple operations and find the average \\ Useful when operations have predictable, recurring costs (!!) \\ Let’s examine a dynamic array that doubles in size when full \\ Each insertion is either O (1) or (m) where m is the current number of elements in array \\ Let’s aggregate all insertions: \\ Assume array starts with size 1 \\ First insertion is 1 itself \\ Secong insertion is 1 itself + 2 for resizing up to 4 \\ Third insertion is 1 itself \\ Fourth insertion is 1 itself + 4 for resizing up to 8 \\ Fifth to seventh insertion are 1 themselves \\ \dots \\ Let n = 2^{k} ⟹ k = \log n \\ Total number of operations for n insertions is: \\ T (n) = (1 + 2 + 4 + 8 + 16 + \dots + n) + n = \\ = \frac{2^{\log n} - 1}{2 - 1} + n = 2 n - 1 \sim 2 n \\ ⟹ T (n) = O (n), T_{A} (n) = \frac{2 n}{n} = O (1) \\ ⟹ Amortized complexity of our insertions is O (1) \\ Although there are heavy operations like the last resizing, that costs O (n) on itself, \\ these operations occur rarely and contribute less to the over-all complexity, \\ than myriads of simple O (1) insertions \end{matrix}

\begin{matrix} Assign pre-paid "credits" to balance cheap and expensive operations \\ Useful when future operations are clearly predictable and can be "pre-paid" \\ Let’s examine a stack with p u s h, p o p and m u l t i P o p methods \\ Each p u s h operation costs O (1) as it is an insertion to an array \\ Each p o p operation costs O (1) as it is a simple extraction from the end of array \\ Each m u l t i P o p operation costs O (m) as it is m extractions \\ Let’s use a trick of overestimating p u s h operation, assume it costs 2 operations \\ but store the unused "credit" for future use \\ Each p u s h would then contribute to a + 1 credit on the balance \\ Each p o p can then become "free" by using this stored "credit" \\ We can safely assume that when executing p o p there will be at least one "credit", \\ or the stack is empty and operation is simply O (1) \\ m u l t i P o p then also becomes "free" as it is "pre-paid" for by all the p u s h operations \\ ⟹ Over-all cost over n p u s h e s and p o p s / m u l t i P o p s is 2 n \\ Which gives us an amortized complexity of O (1) \end{matrix}

\begin{matrix} Use a potential function to track stored work and balance costs instead of "credits" \\ Useful when state changes over time and can be modeled using a function \\ Let’s examine a binary counter \\ Each increment the counter has to flip some number bits \\ For 0000 \to 0001 it’s one bit \\ For 0111 \to 1000 it’s four bits \\ Let us define a work function: w (s) = # of bit flips \\ Let us define a potential function: Φ (s) = # of 1^{'} s in s \\ Let us then define amortized cost of each increment as: \\ f (s) = w (s) + (Φ (s + 1) - Φ (s)) \\ meaning that operations contributing to increase in w will become more expensive \\ while operations, that are expensive on its own will be compensated for reducing potential \\ f (0000) = 1 + (Φ (0001) - Φ (0000)) = 2 \\ f (0001) = 2 + (Φ (0010) - Φ (0001)) = 2 \\ f (0010) = 1 + (Φ (0011) - Φ (0010)) = 2 \\ \dots \\ f (0111) = 4 + (Φ (1000) - Φ (0111)) = 2 \\ f (1111) = 4 + (Φ (0000) - Φ (1111)) = 0 \\ ⟹ T (n) = \sum_{i = 1}^{n} f (s_{i}) \leq \sum_{i = 1}^{n} 2 = 2 n \\ ⟹ T (n) = O (n) \end{matrix}