Folha de consulta de Big-O
Uma referência de Big-O pesquisável e imprimível: complexidade temporal e espacial de arrays, tabelas de hash, árvores, heaps, grafos, ordenação e pesquisa. Grátis.
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
Nenhuma entrada corresponde a “:q”.
Sobre Folha de consulta de Big-O
Esta folha de referência de Big-O coloca a complexidade algorítmica numa única página pesquisável: as próprias classes de complexidade, e depois os custos de tempo e espaço para arrays e arrays dinâmicos, listas ligadas, pilhas e filas, tabelas de hash, árvores de pesquisa binária e árvores equilibradas, heaps, grafos, algoritmos de ordenação, algoritmos de pesquisa, padrões comuns, e notas sobre complexidade de espaço.
É a referência tanto para escolher uma estrutura de dados como para preparar entrevistas: o caso médio e o pior caso para uma pesquisa numa tabela de hash, por que uma árvore equilibrada supera uma BST simples, que ordenações são estáveis e quais são in place, e quanto custam os padrões de dois ponteiros, janela deslizante e memoização.
A folha é gratuita e executada no lado do cliente: filtre linhas em tempo real com a caixa de pesquisa, salte entre secções com o índice fixo, copie qualquer entrada com um clique e imprima a página como referência de secretária.
Como usar Folha de consulta de Big-O
- Abra a folha e comece por Classes de complexidade para fixar O(1), O(log n), O(n), O(n log n) e O(n²).
- Pesquise por uma estrutura ou algoritmo como hash table, quicksort ou BFS para filtrar todas as linhas em tempo real.
- Compare as secções de estruturas de dados quando estiver a escolher entre uma lista, um mapa e uma árvore.
- Clique numa entrada ou no respetivo ícone de cópia para a copiar para a área de transferência.
- Imprima a folha para uma referência de complexidade offline.
Perguntas frequentes
Doze secções: classes de complexidade, arrays e arrays dinâmicos, listas ligadas, pilhas e filas, tabelas de hash, árvores de pesquisa binária e equilibradas, heaps, grafos, algoritmos de ordenação, algoritmos de pesquisa, padrões comuns, e notas sobre complexidade de espaço.
Sim. Onde diferem (pesquisas em tabelas de hash, quicksort, uma BST desequilibrada) a linha indica ambos, para que possa ver o custo quando os dados são adversos.
É construída exatamente para isso: as secções de ordenação e pesquisa mais a secção de padrões comuns cobrem as complexidades que os entrevistadores pedem para dizer em voz alta.
Sim. Os custos de espaço aparecem junto dos custos de tempo, e uma secção final cobre a profundidade da pilha de recursão, in-place versus espaço auxiliar e os compromissos habituais.
Sim, completamente gratuita: pesquisável, imprimível e apresentada no seu navegador sem registo.
Pesquisas populares
cheat sheet big o
tabela de complexidade de tempo
complexidade de estruturas de dados
complexidade de algoritmos de ordenação
tabela de notação big o
tabela de complexidade de espaço
referência de complexidade de algoritmos
Precisa de ajuda?
Encontrou um problema com esta ferramenta? Avise a nossa equipa.