Sign in
Skip to solution
hardDSA

What is amortized analysis?

195 views
01

Understand the problem

Explain amortized cost.

amortized
02

Attempt it yourself

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

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Amortized analysis averages the cost of operations over a sequence, so occasional expensive steps are spread out. Example: a dynamic array's push is O(1) amortized even though some pushes trigger an O(n) resize — doubling makes resizes rare enough.

Solution ready — 2 min read

Classified // press E to declassify

04

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]
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

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

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 124 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track