Amortized Analysis

1
#include <iostream>
2
#include <stdexcept>
3
#include <vector>
4
5
// A minimal dynamic array for int that doubles capacity.
6
// Demonstrates why push_back is O(1) amortized even though resize is expensive.
7
class DynamicArray {
8
private:
9
    int* data_;
10
    size_t size_;
11
    size_t capacity_;
12
13
    void grow() {
14
        // Geometric growth: double the capacity (or set to 1 if currently 0)
15
        size_t newCap = (capacity_ == 0) ? 1 : capacity_ * 2;
16
        int* newData = new int[newCap];
17
        // Copy existing elements (this is the expensive step during some pushes)
18
        for (size_t i = 0; i < size_; ++i) newData[i] = data_[i];
19
        // Delete old buffer and install the new one
20
        delete[] data_;
21
        data_ = newData;
22
        capacity_ = newCap;
23
    }
24
25
public:
26
    DynamicArray() : data_(nullptr), size_(0), capacity_(0) {}
27
    ~DynamicArray() { delete[] data_; }
28
29
    // Disable copying for brevity (a full implementation would add copy/move semantics)
30
    DynamicArray(const DynamicArray&) = delete;
31
    DynamicArray& operator=(const DynamicArray&) = delete;
32
33
    void push_back(int x) {
34
        if (size_ == capacity_) {
35
            // Occasional expensive resize: O(size_)
36
            grow();
37
        }
38
        // Usual cheap insertion: O(1)
39
        data_[size_++] = x;
40
    }
41
42
    int& operator[](size_t i) {
43
        if (i >= size_) throw std::out_of_range("index out of range");
44
        return data_[i];
45
    }
46
47
    size_t size() const { return size_; }
48
    size_t capacity() const { return capacity_; }
49
};
50
51
int main() {
52
    DynamicArray a;
53
    // Insert many items; observe occasional capacity jumps (expensive events)
54
    for (int i = 0; i < 20; ++i) {
55
        size_t beforeCap = a.capacity();
56
        a.push_back(i);
57
        size_t afterCap = a.capacity();
58
        if (afterCap != beforeCap) {
59
            std::cout << "Resized: capacity from " << beforeCap << " to " << afterCap << "\n";
60
        }
61
    }
62
63
    // Verify contents
64
    std::cout << "Values: ";
65
    for (size_t i = 0; i < a.size(); ++i) std::cout << a[i] << ' ';
66
    std::cout << "\n";
67
68
    // Amortized note: There were only O(log n) resizes; most pushes were O(1).
69
    return 0;
70
}
71

1
#include <iostream>
2
#include <vector>
3
#include <string>
4
5
// A simple binary counter using least significant bit at index 0.
6
// Increment may flip many bits, but the amortized flips per increment are O(1).
7
class BinaryCounter {
8
public:
9
    std::vector<int> bits; // store 0/1
10
11
    BinaryCounter() {}
12
13
    // Increment the counter and return the number of bit flips performed.
14
    int increment() {
15
        int flips = 0;
16
        size_t i = 0;
17
        // Propagate carry through trailing 1s: 1 -> 0 (each flip counted)
18
        while (i < bits.size() && bits[i] == 1) {
19
            bits[i] = 0;
20
            ++flips;
21
            ++i;
22
        }
23
        // Set the first 0 to 1 (or append a new 1 if carry extends past MSB)
24
        if (i == bits.size()) bits.push_back(1);
25
        else bits[i] = 1;
26
        ++flips;
27
        return flips;
28
    }
29
30
    std::string str() const {
31
        if (bits.empty()) return "0";
32
        std::string s;
33
        for (size_t i = bits.size(); i-- > 0; ) s.push_back('0' + bits[i]);
34
        return s;
35
    }
36
};
37
38
int main() {
39
    BinaryCounter c;
40
    long long totalFlips = 0;
41
    int m = 16; // perform 16 increments
42
    for (int i = 0; i < m; ++i) {
43
        int flips = c.increment();
44
        totalFlips += flips;
45
        std::cout << "After increment " << (i+1) << ": " << c.str()
46
                  << ", flips this time = " << flips << "\n";
47
    }
48
    std::cout << "Total flips over " << m << " increments = " << totalFlips << "\n";
49
    // Theory says total flips < 2m, so average flips per increment < 2 (O(1) amortized).
50
    return 0;
51
}
52

1
#include <iostream>
2
#include <vector>
3
4
// Disjoint Set Union with path compression and union by rank.
5
// Supports near-constant amortized time per operation: O(alpha(n)).
6
class DSU {
7
    std::vector<int> parent;
8
    std::vector<int> rank; // approximate tree height
9
public:
10
    explicit DSU(int n) : parent(n), rank(n, 0) {
11
        for (int i = 0; i < n; ++i) parent[i] = i;
12
    }
13
14
    int find(int x) {
15
        // Path compression: recursively set parent to root
16
        if (parent[x] != x) parent[x] = find(parent[x]);
17
        return parent[x];
18
    }
19
20
    bool unite(int a, int b) {
21
        a = find(a); b = find(b);
22
        if (a == b) return false;
23
        // Union by rank: attach shallower tree under deeper one
24
        if (rank[a] < rank[b]) std::swap(a, b);
25
        parent[b] = a;
26
        if (rank[a] == rank[b]) ++rank[a];
27
        return true;
28
    }
29
};
30
31
int main() {
32
    DSU dsu(10);
33
    dsu.unite(1, 2);
34
    dsu.unite(2, 3);
35
    dsu.unite(4, 5);
36
    dsu.unite(6, 7);
37
    dsu.unite(5, 6);
38
    // Multiple finds will become faster as paths compress
39
    for (int i = 1; i <= 7; ++i) {
40
        std::cout << "find(" << i << ") = " << dsu.find(i) << "\n";
41
    }
42
    // Repeated queries after compression are essentially O(1) amortized
43
    for (int i = 1; i <= 7; ++i) {
44
        std::cout << "find(" << i << ") again = " << dsu.find(i) << "\n";
45
    }
46
    return 0;
47
}
48