Amortized Analysis

• Amortized Analysis animated explanation
• Used for algorithms where occasional operations are more costly but other remaining operations are faster.
• provides a useful way to analyse algorithms that perform a sequence of operations where some operations are more expensive than others, as it provides a guaranteed upper bound on the average time complexity of each operation, rather than the worst-case time complexity.

Aggregate Method
- Simplest method for amortized analysis.\(\(Amortized \ Cost\ Per\ operation \ = \ \frac{tota\ cost\ for \ all\ operations}{No\ of \ operations}\)\)
Accounting Method
- Assign a random cost [amortized cost Ci' ] to the ith operation, where 1 unit of amount pays for 1 unit of work - The actual cost of operation is less than the allocated amount, the remaining amount is saved and then used later for costly operation - This bank balance (remaining amount) of ours must never go below zero! - Actual cost incurred must always be <= amortized cost assigned Actual Cost -> Ci Amortized Cost -> Ci' (Ci Cap)

Potential Method
- At any given point, there a is a potential in the data structure - Initial Potential of Data Structure = \(D_0\) - Operation i transforms DS from '\(D_{i-1}\)->\(D_i\)' - Amortized Cost = Actual Cost + Change in Potential \(\(C_i'\ = \ C_i \ + \phi (D_i) -\ \phi(D_{i-1})\)\) - \(\phi(D_i)\) -> R ; Potential function - Potential functions are predefined according to the data structure

Potential Functions
    Stack -> No. of elements
    Dynamic List -> PS. Log i is ceiled here$$2i\ -\ 2^{\lceil log(i) \rceil}$$