Soluções avançadas escondem o custo na estrutura de dados. Uma operação de heap é O(log do tamanho do heap), não O(1). Uma BFS visita uma vez cada nó e cada aresta alcançáveis. Uma recursão com memoização custa o número de estados distintos vezes o trabalho de cada estado, mais a profundidade da pilha de chamadas em espaço.
Alguns custos são amortizados: um array dinâmico que dobra de tamanho quando enche copia tudo de vez em quando, mas n inserções ainda custam O(n) no total, então uma inserção é O(1) em média e O(n) no pior caso. Diga “amortizado” quando for isso que você quer dizer.
Em grafos, use V para os nós e E para as arestas, e diga qual termo domina. O Dijkstra com um heap binário é O((V + E) log V); a BFS é O(V + E). Em programação dinâmica, conte o tamanho da tabela: duas strings de comprimentos m e n dão uma tabela de m por n, e manter apenas duas linhas reduz o espaço a O(min(m, n)).
Custo = número de estados ou operações vezes o custo de cada um.