Amortized Analysis — The LinkedList Cache Locality Trap

package io.thecodeforge.analysis;

import java.util.ArrayList;

/**
 * Illustrates why worst-case-per-operation misleads for amortized structures.
 *
 * The naive reading: ArrayList.add() is O(n) worst-case, so 1024 inserts
 * should cost O(1024 * 1024) = O(1M) operations.
 *
 * The amortized reality: total cost is O(n), not O(n^2).
 * We measure actual work done and confirm the amortized bound empirically.
 */
public class AmortizedIntro {

    public static void main(String[] args) {
        int n = 1024;
        long actualWork = 0;

        // Manually simulate ArrayList growth to count real operations.
        int[] internalArray = new int[1];
        int size = 0;
        int resizeEvents = 0;

        for (int i = 0; i < n; i++) {
            if (size == internalArray.length) {
                // Resize: copy all elements to new array (2x growth)
                int[] newArray = new int[internalArray.length * 2];
                for (int j = 0; j < size; j++) {
                    newArray[j] = internalArray[j];
                    actualWork++;  // Count each copy as one unit of work
                }
                internalArray = newArray;
                resizeEvents++;
            }
            internalArray[size++] = i;
            actualWork++;  // Count the insert itself
        }

        System.out.println("Elements inserted : " + n);
        System.out.println("Resize events      : " + resizeEvents);
        System.out.println("Total actual work  : " + actualWork);
        System.out.println("Naive worst-case   : " + ((long) n * n) + "  [O(n^2) — wildly wrong]");
        System.out.println("Amortized bound    : " + (3L * n) + "  [O(n) — correct]");
        System.out.printf ("Work per insert    : %.2f  [O(1) amortized]%n",
                           (double) actualWork / n);
    }
}

package io.thecodeforge.ds;

import java.util.ArrayList;
import java.util.List;

/**
 * Stack supporting push, pop, and multipop.
 *
 * Aggregate analysis:
 *   - Across any n operations, total pushes <= n
 *   - Total pops (including multipop) <= total pushes <= n
 *   - Therefore total cost of all n operations <= 2n = O(n)
 *   - Amortized cost per operation: O(n)/n = O(1)
 *
 * The key insight: you cannot pop what was never pushed.
 * That single observation bounds the total cost of all pop operations
 * regardless of the sequence order — this is what makes it aggregate.
 */
public class StackWithMultipop<T> {
    private final List<T> stack = new ArrayList<>();
    private long totalPushes = 0;
    private long totalPops = 0;

    public void push(T item) {
        stack.add(item);  // O(1) amortized
        totalPushes++;
    }

    public T pop() {
        if (stack.isEmpty()) {
            throw new IllegalStateException("Stack underflow");
        }
        totalPops++;
        return stack.remove(stack.size() - 1);  // O(1)
    }

    /**
     * Pops up to k elements.
     * Worst-case single call: O(min(k, size)).
     * Amortized over n operations: O(1).
     *
     * Why: every element popped here was previously pushed.
     * Total pops across the entire operation sequence cannot exceed total pushes.
     */
    public void multipop(int k) {
        int pops = Math.min(k, stack.size());
        for (int i = 0; i < pops; i++) {
            stack.remove(stack.size() - 1);
            totalPops++;
        }
    }

    public int size() { return stack.size(); }

    public static void main(String[] args) {
        StackWithMultipop<Integer> s = new StackWithMultipop<>();

        // Sequence: 10 pushes, multipop(5), 3 pushes, multipop(8)
        // Total pushes: 13. Total pops: min(5,10) + min(8,5) = 5 + 5 = 10.
        // Total operations n: 10 + 1 + 3 + 1 = 15.
        // Total work: 13 pushes + 10 pops = 23 <= 2n = 30. Amortized: O(1).
        for (int i = 0; i < 10; i++) s.push(i);
        s.multipop(5);
        for (int i = 10; i < 13; i++) s.push(i);
        s.multipop(8);  // Only 5 remain after first multipop — pops 5, not 8

        System.out.println("Operations completed : 15");
        System.out.println("Total pushes         : " + s.totalPushes);
        System.out.println("Total pops           : " + s.totalPops);
        System.out.println("Total work           : " + (s.totalPushes + s.totalPops));
        System.out.println("Bound (2n)           : " + (2 * 15));
        System.out.println("Amortized per op     : O(1) [" +
            (double)(s.totalPushes + s.totalPops) / 15 + " actual]");
        System.out.println("Stack size after ops : " + s.size());
    }
}

package io.thecodeforge.analysis;

/**
 * Accounting method analysis for a dynamic array.
 *
 * Charge per insert: $3
 *   $1 — pays for the actual array write
 *   $1 — stored as credit on this element (pays for its own copy on resize)
 *   $1 — stored as credit on a 'mirror' element in the first half (pays for that copy)
 *
 * Resize invariant: when capacity doubles from n to 2n,
 *   the n elements have accumulated n credits — exactly enough
 *   to pay for copying all n elements to the new array.
 *
 * Credit balance invariant: credits must NEVER go negative.
 * If they do, the charge is too low and the scheme is broken.
 *
 * Result: total charged = 3n, total actual < 3n, amortized per insert = O(1).
 */
public class AccountingMethodDemo {

    private int[] data;
    private int size;
    private long credits;          // Running credit balance across all stored elements
    private long totalCharged;     // Cumulative amount charged across all inserts
    private long totalActualCost;  // Cumulative actual work done (writes + copies)

    public AccountingMethodDemo() {
        data = new int[1];
        size = 0;
        credits = 0;
        totalCharged = 0;
        totalActualCost = 0;
    }

    public void add(int item) {
        long charge = 3;  // Amortized charge per insert — proven sufficient below
        totalCharged += charge;

        long actualCost = 1;  // The insert itself: one array write

        if (size == data.length) {
            // Resize: copy all current elements to a new 2x array
            // This is the expensive operation — paid for by stored credits
            actualCost += size;  // size copy operations, each costing 1
            int[] newData = new int[data.length * 2];
            System.arraycopy(data, 0, newData, 0, size);
            data = newData;
        }

        data[size++] = item;
        totalActualCost += actualCost;
        credits = totalCharged - totalActualCost;

        // THE INVARIANT: credits must never go negative.
        // A negative balance means the charge was insufficient — the proof breaks.
        if (credits < 0) {
            throw new IllegalStateException(
                "Credit balance went negative at insert " + size +
                " — charge of $3 per insert is insufficient. Proof is invalid.");
        }
    }

    public static void main(String[] args) {
        AccountingMethodDemo demo = new AccountingMethodDemo();

        System.out.printf("%-10s %-12s %-10s %-10s %-14s %-14s%n",
            "Insert", "Actual Cost", "Charged", "Credits", "Total Actual", "Total Charged");
        System.out.println("-".repeat(75));

        for (int i = 0; i < 16; i++) {
            long actualBefore = demo.totalActualCost;
            demo.add(i);
            long actualThisOp = demo.totalActualCost - actualBefore;

            System.out.printf("%-10d %-12d %-10s %-10d %-14d %-14d%n",
                i,
                actualThisOp,
                "$3",
                demo.credits,
                demo.totalActualCost,
                demo.totalCharged);
        }

        System.out.println();
        System.out.println("Inserts           : 16");
        System.out.println("Total charged     : $" + demo.totalCharged + "  (16 * $3)");
        System.out.println("Total actual      : " + demo.totalActualCost);
        System.out.println("Remaining credits : " + demo.credits);
        System.out.println("Amortized / insert: $" + demo.totalCharged / 16 + "  = O(1)");
        System.out.println("Credit invariant  : never violated [verified above]");
    }
}

package io.thecodeforge.analysis;

import java.util.ArrayList;
import java.util.List;

/**
 * Potential method analysis for a stack with multipop.
 *
 * Potential function: Φ(D) = number of items in the stack.
 *
 * Amortized cost formula: â(op) = actual(op) + Φ(after) - Φ(before)
 *
 * Per operation:
 *   push(x)    : actual=1, ΔΦ=+1, amortized = 1+1 = 2
 *   pop()      : actual=1, ΔΦ=-1, amortized = 1-1 = 0
 *   multipop(k): actual=min(k,|D|), ΔΦ=-min(k,|D|), amortized = 0
 *
 * Proof bound:
 *   Total amortized = Σ â(op_i) = Σ actual(op_i) + Φ(final) - Φ(initial)
 *   Since Φ >= 0 always and Φ(initial) = 0 (empty stack):
 *   Σ actual(op_i) <= Σ â(op_i)
 *   => Total actual cost <= total amortized cost. QED.
 *
 * Across n operations: total amortized <= 2n (only pushes contribute 2 each).
 * Therefore total actual <= 2n => amortized O(1) per operation.
 */
public class PotentialMethodDemo {
    private final List<Integer> stack = new ArrayList<>();
    private long totalAmortized = 0;
    private long totalActual = 0;

    /** Φ(D) = number of items in the stack. Always >= 0. */
    private int phi() {
        return stack.size();
    }

    public void push(int item) {
        int phiBefore = phi();
        stack.add(item);
        int actual = 1;
        int deltaPhi = phi() - phiBefore;   // +1: stack grew by one element
        int amortized = actual + deltaPhi;  // 1 + 1 = 2
        totalActual += actual;
        totalAmortized += amortized;
        System.out.printf("push(%2d) | Φ_before=%2d | actual=%d | ΔΦ=%+d | amortized=%d | Φ_after=%2d%n",
            item, phiBefore, actual, deltaPhi, amortized, phi());
    }

    public int pop() {
        if (stack.isEmpty()) throw new IllegalStateException("Stack underflow");
        int phiBefore = phi();
        int item = stack.remove(stack.size() - 1);
        int actual = 1;
        int deltaPhi = phi() - phiBefore;   // -1: stack shrank by one element
        int amortized = actual + deltaPhi;  // 1 + (-1) = 0
        totalActual += actual;
        totalAmortized += amortized;
        System.out.printf("pop()    | Φ_before=%2d | actual=%d | ΔΦ=%+d | amortized=%d | Φ_after=%2d%n",
            phiBefore, actual, deltaPhi, amortized, phi());
        return item;
    }

    public void multipop(int k) {
        int phiBefore = phi();
        int pops = Math.min(k, stack.size());
        for (int i = 0; i < pops; i++) {
            stack.remove(stack.size() - 1);
        }
        int actual = pops;
        int deltaPhi = phi() - phiBefore;   // -pops: potential drops by number popped
        int amortized = actual + deltaPhi;  // pops + (-pops) = 0
        totalActual += actual;
        totalAmortized += amortized;
        System.out.printf("multi(%d) | Φ_before=%2d | actual=%d | ΔΦ=%+d | amortized=%d | Φ_after=%2d%n",
            k, phiBefore, actual, deltaPhi, amortized, phi());
    }

    public static void main(String[] args) {
        PotentialMethodDemo demo = new PotentialMethodDemo();

        System.out.println("Operation  | Φ_before | actual | ΔΦ  | amortized | Φ_after");
        System.out.println("-".repeat(65));

        demo.push(1);
        demo.push(2);
        demo.push(3);
        demo.push(4);
        demo.multipop(3);
        demo.push(5);
        demo.push(6);
        demo.pop();
        demo.multipop(10);  // Only 2 remain — pops 2, not 10

        System.out.println();
        System.out.println("Total actual cost    : " + demo.totalActual);
        System.out.println("Total amortized cost : " + demo.totalAmortized);
        System.out.println("Φ(final)             : " + demo.phi());
        System.out.println("Bound check          : actual (" + demo.totalActual +
            ") <= amortized (" + demo.totalAmortized + ")? " +
            (demo.totalActual <= demo.totalAmortized));
        System.out.println();
        System.out.println("Interpretation: Φ(final) = " + demo.phi() +
            " stored potential was never paid out — actual was less than amortized.");
        System.out.println("This confirms: Σ actual <= Σ amortized. The bound holds.");
    }
}

package io.thecodeforge.ds;

/**
 * Dynamic array with instrumented resize tracking.
 * Growth factor: 2x (clearer math than Java's 1.5x — same asymptotic result).
 *
 * After n inserts:
 *   - Resize copy costs: 1 + 2 + 4 + ... + n/2 = n-1 < n  (geometric series)
 *   - Insert costs: n  (one per insert)
 *   - Total cost: < 2n  => amortized per insert: < 2 = O(1)
 *
 * The geometric series is the key: Σ(2^i) for i=0 to log2(n)-1 = n-1.
 * Each term is half the next resize cost — earlier resizes are tiny
 * relative to the final one. That's why the sum stays bounded by 2n.
 */
public class DynamicArray<T> {
    private Object[] data;
    private int size;
    private int resizeCount;
    private long totalCopyCost;  // Total elements copied across all resizes
    private long totalInsertCost; // Always equal to size after n inserts

    public DynamicArray() {
        data = new Object[1];
        size = 0;
        resizeCount = 0;
        totalCopyCost = 0;
        totalInsertCost = 0;
    }

    public void add(T item) {
        if (size == data.length) {
            resize(data.length * 2);
        }
        data[size++] = item;
        totalInsertCost++;
    }

    private void resize(int newCapacity) {
        resizeCount++;
        totalCopyCost += size;  // Copying 'size' elements to the new array
        Object[] newData = new Object[newCapacity];
        System.arraycopy(data, 0, newData, 0, size);
        data = newData;
        System.out.printf("  [resize] capacity %d -> %d | copy cost this resize: %d | "
            + "cumulative copy cost: %d%n",
            newCapacity / 2, newCapacity, size, totalCopyCost);
    }

    public int size()     { return size; }
    public int capacity() { return data.length; }

    public static void main(String[] args) {
        int n = 1024;
        DynamicArray<Integer> arr = new DynamicArray<>();

        System.out.println("Inserting " + n + " elements (resize events printed inline):\n");
        for (int i = 0; i < n; i++) {
            arr.add(i);
        }

        long totalCost = arr.totalInsertCost + arr.totalCopyCost;
        System.out.println();
        System.out.println("=== Results ===");
        System.out.println("Elements inserted     : " + n);
        System.out.println("Final capacity        : " + arr.capacity());
        System.out.println("Resize events         : " + arr.resizeCount
            + "  (= log2(" + n + ") = 10)");
        System.out.println("Total insert cost     : " + arr.totalInsertCost);
        System.out.println("Total copy cost       : " + arr.totalCopyCost
            + "  (= n-1 for 2x growth)");
        System.out.println("Total combined cost   : " + totalCost);
        System.out.println("Theoretical bound (2n): " + (2 * n));
        System.out.printf ("Amortized per insert  : %.4f  (< 2 = O(1))%n",
            (double) totalCost / n);
        System.out.println();
        System.out.println("Memory observation: final array has " + arr.capacity()
            + " slots but " + n + " elements — zero wasted capacity (exact power of 2 example).");
    }
}