hardDSA

What is amortized analysis?

Q: What is amortized analysis?

**Intuition.** Amortized analysis asks for the *average* cost of an operation **over a sequence**, not the worst single call. Some operations are occasionally expensive but rare enough that, spread out, each one is cheap. The classic example: appending to a **dynamic array** is O(1) amortized even though some appends trigger an O(n) resize. push cost: mostly 1, occasional spike when capacity doubles <rect x="66" y="92" width="20" height="28" fill

195 views

Understand the problem

Explain amortized cost.

amortized

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

Read the code

Dynamic array with doubling

Run Playground

class DynamicArray:
    def __init__(self):
        self.data = [None]
        self.size = 0

    def push(self, x):
        if self.size == len(self.data):    # full -> O(n) resize, but rare
            new = [None] * (2 * len(self.data))
            for i in range(self.size):
                new[i] = self.data[i]
            self.data = new
        self.data[self.size] = x           # O(1) amortized
        self.size += 1


# --- demo ---  5 pushes trigger resizes at cap 1,2,4 -> still O(1) amortized
arr = DynamicArray()
for x in range(5): arr.push(x)
print(arr.size, arr.data[:arr.size])   # 5 [0, 1, 2, 3, 4]

Join the discussion

Discussion (0)

No responses yet. Be the first to share what you think.

How does Dijkstra's algorithm work?

How do you find the top K frequent elements?