Las soluciones avanzadas esconden su coste en la estructura de datos. Una operación de montículo es O(log del tamaño del montículo), no O(1). Una BFS visita una vez cada nodo y cada arista alcanzables. Una recursión con memoización cuesta el número de estados distintos por el trabajo de cada estado, más la profundidad de la pila de llamadas en espacio.
Algunos costes son amortizados: un array dinámico que dobla su capacidad al llenarse lo copia todo de vez en cuando, pero n inserciones siguen costando O(n) en total, así que una inserción es O(1) de media y O(n) en el peor caso. Di «amortizado» cuando quieras decir eso.
En los grafos, usa V para los nodos y E para las aristas, y di qué término domina. Dijkstra con un montículo binario es O((V + E) log V); BFS es O(V + E). En programación dinámica, cuenta el tamaño de la tabla: dos cadenas de longitudes m y n dan una tabla de m por n, y quedarte solo con dos filas reduce el espacio a O(min(m, n)).
Coste = número de estados u operaciones por el coste de cada uno.