BEGINNER · 10 MIN · FREE LESSON

Time vs space complexity

Explore time vs space complexity through a visual, step-by-step model.

Size 8

default
? comparing
↔ moving
✓ visited
Q queued
✓ done

Compare duplicate detection with and without extra memory.

Code language

Speed

1 / 23

Live variables

Operation counters

comparisons: 0
swaps: 0
reads: 0
writes: 0
pairChecks: 0
setLookups: 0

Complexity · Naive O(n²); hash expected O(n)

best: O(1) early duplicate
average: Naive O(n²); hash expected O(n)
worst: Naive O(n²); hash expected O(n)
space: Naive O(1); hash O(n)

Extra memory remembers previously seen keys, trading a nested pair scan for expected constant-time set membership checks.

n=8

n=16

221

n=32

n=64

Measured reads + comparisons, seed 42. Plotted sample sizes respect each lesson’s explicit input limits.

Keyboard: Space play/pause · ←/→ step · R restart · 1–5 speed. Reduced motion disables transitions.

Time Vs Space Complexity

Hook

Write down the names you have seen instead of repeatedly comparing everyone with everyone.

Watch

Spend memory to save repeated work. Explore the validated presets and edit the input to check a boundary case.

How it works

Try a constant-space scan of every pair.
Try a set that remembers earlier keys.
Compare the work counters and stored-key count.

Try it

Predict each decision before advancing. The player checks against the real model and explains why an alternative move fails.

Complexity

The pair method is quadratic without an early duplicate. Hash-set lookup is expected constant time per key but uses linear extra memory. The chart labels identify actual counters or explicitly modeled recurrence work; display snapshots are not charged to the underlying algorithm.

Code

Switch among JavaScript, Python, Java and C++. The active conceptual stage and live variables connect the code to the trace.

When to use

Use this trade-off when remembering previous work avoids repeated scans.

Interview pitfalls

Expected hash-table performance is not a universal worst-case guarantee. Extra memory must be counted separately from time.

Quiz

Test the invariant and cost model below, then explain the result on a different preset.

MAKE IT STICK

Quick knowledge check

Progress saves on this device and merges with your account after sign-in.

Your notebook

Private lesson notes

0 / 5000 · Saved on this device; synced when signed in.

Loading interactive lesson…

Next: Recursion basics →