Cheat sheet Big-O
Una referenza Big-O consultabile e stampabile: complessità di tempo e spazio per array, tabelle hash, alberi, heap, grafi, ordinamento e ricerca. Gratis.
Complexity classes
12O(1): constant
Same cost regardless of input size
O(log n): logarithmic
Halves the problem each step
O(n): linear
Touches every element once
O(n log n): linearithmic
Best possible comparison sort
O(n²): quadratic
Every pair: nested loops over input
O(n³): cubic
Triple nesting, e.g. naive matrix multiply
O(2^n): exponential
Doubles per element: all subsets
O(n!): factorial
All orderings: brute-force permutations
n = 10^6: O(n log n) ≈ 2×10^7 ops
Fine: well under a second
n = 10^6: O(n²) = 10^12 ops
Too slow: think minutes to hours
Rule: drop constants and lower terms
O(3n² + 5n) is just O(n²)
Amortized O(1)
Occasionally slow, cheap on average
Arrays & dynamic arrays
11Access by index: O(1)
Direct address arithmetic
Search (unsorted): O(n)
Must scan every element
Search (sorted): O(log n)
Binary search on sorted data
Append (dynamic): O(1) amortized
Occasional resize copies all
Insert at front/middle: O(n)
Shifts all later elements
Delete at end: O(1)
No shifting required
Delete at front/middle: O(n)
Shifts elements to close the gap
Resize (grow ×2): O(n)
Copy into a bigger buffer
Slice/copy: O(k)
Proportional to slice length
Space: O(n)
May hold up to 2× capacity slack
Cache-friendly: contiguous memory
Real-world edge over linked lists
Linked lists
10Access by index: O(n)
Must walk from the head
Search: O(n)
Linear scan, no shortcuts
Insert/delete at head: O(1)
Repoint the head pointer
Insert/delete at tail: O(1) with tail ptr
O(n) without one (singly)
Insert after known node: O(1)
The big win over arrays
Delete known node (doubly): O(1)
Prev pointer makes unlink cheap
Delete known node (singly): O(n)
Must find the predecessor
Reverse: O(n) time, O(1) space
Classic pointer-flip interview task
Detect cycle: O(n), O(1) space
Floyd's tortoise and hare
Space: O(n) plus pointer overhead
1–2 pointers per node
Stacks & queues
10Stack push/pop/peek: O(1)
LIFO: last in, first out
Stack search: O(n)
No random access
Queue enqueue/dequeue: O(1)
FIFO: first in, first out
Deque push/pop both ends: O(1)
Double-ended queue
Queue via 2 stacks: O(1) amortized
Classic interview construction
Min-stack: O(1) getMin
Track min alongside each push
Monotonic stack: O(n) total
Next greater element problems
Stack use: DFS, undo, call stack
Recursion is an implicit stack
Queue use: BFS, schedulers, buffers
Level-order processing
Space: O(n)
One slot per stored element
Hash tables
11Insert: O(1) avg, O(n) worst
Worst = all keys collide
Lookup: O(1) avg, O(n) worst
Hash, then probe the bucket
Delete: O(1) avg, O(n) worst
Same story as lookup
Resize/rehash: O(n)
Triggered past the load factor
Load factor ~0.7
Typical resize threshold
Chaining
Collisions become linked lists
Open addressing
Probe for the next free slot
Ordered iteration: not provided
Use a tree map if order matters
Hash set membership: O(1) avg
The go-to de-dupe structure
Space: O(n)
Plus empty buckets overhead
Pattern: trade O(n) space for O(1) lookups
Two-sum in one pass
Binary search trees & balanced trees
12BST search/insert/delete: O(h)
h = tree height
BST average: O(log n)
Random inserts stay bushy
BST worst: O(n)
Sorted inserts make a chain
AVL all ops: O(log n) guaranteed
Strict balance, fast lookups
Red-black all ops: O(log n)
Looser balance, faster writes
B-tree all ops: O(log n)
Wide nodes: databases, disks
In-order traversal: O(n)
Visits keys in sorted order
Min/max: O(log n) balanced
Walk far left / far right
Successor/predecessor: O(log n)
Ordered neighbors of a key
Range query: O(log n + k)
k = number of results
Trie lookup: O(L)
L = key length, not item count
Space: O(n)
2–3 pointers per node
Heaps
10Peek min/max: O(1)
Root holds the extreme
Insert: O(log n)
Bubble up to restore order
Extract min/max: O(log n)
Pop root, sift down
Build heap from array: O(n)
Heapify beats n inserts
Search arbitrary key: O(n)
Heaps are not for lookups
Decrease-key: O(log n)
Core of Dijkstra's algorithm
Top-k of n items: O(n log k)
Keep a size-k heap
Two heaps: O(log n) per insert
Running median pattern
Stored as an array
Children at 2i+1, 2i+2
Space: O(n)
No pointers needed
Graphs
12Adjacency list space: O(V + E)
Best for sparse graphs
Adjacency matrix space: O(V²)
Best for dense graphs
Edge check: list O(deg), matrix O(1)
The core trade-off
Iterate neighbors: list O(deg), matrix O(V)
Lists win for traversal
BFS / DFS: O(V + E)
With an adjacency list
Topological sort: O(V + E)
DAG ordering (Kahn / DFS)
Dijkstra: O((V + E) log V)
Binary heap, no negative edges
Bellman-Ford: O(V·E)
Handles negative edges
Floyd-Warshall: O(V³)
All-pairs shortest paths
Prim / Kruskal MST: O(E log V)
Minimum spanning tree
Union-Find: O(α(n)) ≈ O(1)
With rank + path compression
A*: O(E) best case
Heuristic-guided Dijkstra
Sorting algorithms
13Bubble sort: O(n²), best O(n)
O(1) space; only teaching value
Insertion sort: O(n²), best O(n)
O(1) space; great when nearly sorted
Selection sort: O(n²) always
O(1) space; fewest swaps
Merge sort: O(n log n) always
O(n) space; stable; predictable
Quick sort: avg O(n log n), worst O(n²)
O(log n) space; fastest in practice
Heap sort: O(n log n) always
O(1) space; not stable
Tim sort: O(n log n), best O(n)
Python/Java built-in; stable
Counting sort: O(n + k)
k = value range; not comparison
Radix sort: O(d·(n + k))
d = digits; ints and strings
Bucket sort: avg O(n + k), worst O(n²)
Uniformly distributed input
Shell sort: ~O(n^1.3)
Gap-based insertion sort
Comparison-sort lower bound: Ω(n log n)
Cannot do better by comparing
Stable: merge, insertion, tim, counting
Equal keys keep their order
Searching algorithms
11Linear search: O(n)
Only option for unsorted data
Binary search: O(log n)
Sorted arrays only
Binary search space: O(1) iterative
O(log n) if recursive
Hash lookup: O(1) avg
Fastest membership test
BST search: O(log n) balanced
Also gives sorted neighbors
Trie prefix search: O(L)
Autocomplete workhorse
BFS shortest path (unweighted): O(V + E)
First hit is the shortest
lower_bound / bisect: O(log n)
First element >= target
Quickselect (k-th element): avg O(n)
Worst O(n²); no full sort
Ternary search: O(log n)
Peak of a unimodal function
Interpolation search: avg O(log log n)
Uniform sorted data only
Common patterns
12Two pointers: O(n)
Pair sums in a sorted array
Sliding window: O(n)
Best subarray of size/condition k
Fast & slow pointers: O(n)
Cycle detection, list middle
Prefix sums: O(n) build, O(1) query
Range-sum questions
Binary search on answer: O(n log range)
"Min capacity to ship in D days"
Monotonic stack: O(n)
Next greater / histogram area
Backtracking: O(2^n) or O(n!)
Subsets / permutations search
Memoized DP: states × transition cost
Kills exponential recursion
Greedy: usually O(n log n)
Sort, then one linear pass
Divide & conquer: T(n) = 2T(n/2) + O(n)
Master theorem: O(n log n)
Bit manipulation: O(1) per op
Sets of <=64 items in an int
Meet in the middle: O(2^(n/2))
Halves an exponential search
Space complexity notes
11In-place: O(1) extra space
Quick sort, heap sort, reversal
Recursion costs stack space
Depth d means O(d) memory
DFS space: O(h) / O(V) worst
h = depth of recursion
BFS space: O(w)
w = widest level (can be n/2)
Merge sort: O(n) auxiliary
The price of stability
Memoization: O(#states)
Time saved, memory spent
DP table row trick: O(n²) → O(n)
Keep only the previous row
Hash-based de-dupe: O(n) space
vs O(1) sort-first approach
Tail recursion: O(1) if optimized
Not guaranteed in every language
Streaming: O(1) or O(k) space
One pass, constant memory
Always state time AND space
Interviews expect both
Nessuna voce corrisponde a “:q”.
Informazioni su Cheat sheet Big-O
Questo cheat sheet sulla notazione Big-O mette la complessità algoritmica in un'unica pagina consultabile: le classi di complessità stesse, poi i costi di tempo e spazio per array e array dinamici, liste collegate, stack e code, tabelle hash, alberi binari di ricerca ed alberi bilanciati, heap, grafi, algoritmi di ordinamento, algoritmi di ricerca, pattern comuni, e note sulla complessità spaziale.
È il riferimento sia per scegliere una struttura dati sia per la preparazione ai colloqui: il caso medio e peggiore per una ricerca in una tabella hash, perché un albero bilanciato batte un semplice BST, quali ordinamenti sono stabili e quali sono in-place, e quanto costano i pattern two-pointer, sliding-window e memoization.
Il foglio è gratuito e lato client: filtra le righe dal vivo con la casella di ricerca, salta tra le sezioni con l'indice fisso, copia qualsiasi voce con un clic e stampa la pagina come riferimento da scrivania.
Come usare Cheat sheet Big-O
- Apri il foglio e inizia con Classi di complessità per fissare O(1), O(log n), O(n), O(n log n) e O(n²).
- Cerca una struttura o un algoritmo come hash table, quicksort o BFS per filtrare ogni riga dal vivo.
- Confronta le sezioni sulle strutture dati quando stai scegliendo tra una lista, una mappa e un albero.
- Fai clic su una voce o sulla sua icona di copia per copiarla negli appunti.
- Stampa il foglio per un riferimento offline sulla complessità.
Domande frequenti
Dodici sezioni: classi di complessità, array e array dinamici, liste collegate, stack e code, tabelle hash, alberi di ricerca binaria e bilanciati, heap, grafi, algoritmi di ordinamento, algoritmi di ricerca, pattern comuni, e note sulla complessità spaziale.
Sì. Dove differiscono (ricerche in tabelle hash, quicksort, un BST non bilanciato) la riga indica entrambi, così puoi vedere il costo quando i dati sono avversi.
È costruito esattamente per questo: le sezioni su ordinamento e ricerca più la sezione sui pattern comuni coprono le complessità che gli intervistatori ti chiedono di enunciare ad alta voce.
Sì. I costi spaziali compaiono accanto ai costi temporali, e una sezione finale copre la profondità dello stack di ricorsione, lo spazio in-place rispetto a quello ausiliario e i soliti compromessi.
Sì, completamente gratuito: consultabile, stampabile e visualizzato nel tuo browser senza registrazione.
Ricerche popolari
cheat sheet big o
tabella complessità temporale
complessità strutture dati
complessità algoritmi di ordinamento
tabella notazione big o
tabella complessità spaziale
riferimento complessità algoritmi
Hai bisogno di aiuto?
Hai riscontrato un problema con questo strumento? Faccelo sapere.