高度な解法は、そのコストをデータ構造の中に隠しています。ヒープ操作はO(1)ではなく、O(ヒープのサイズのlog)です。BFSは到達可能なすべてのノードと辺を一度ずつ訪問します。メモ化再帰のコストは、異なる状態の数 × 状態ごとの処理量で、空間にはさらにコールスタックの深さが加わります。
償却されるコストもあります:満杯になると倍になる動的配列はときどきすべてをコピーしますが、n回の追加は合計でO(n)に収まるので、一回の追加は平均でO(1)、最悪でO(n)です。償却の意味で言うときは「償却」と明言してください。
グラフでは、ノード数にV、辺の数にEを使い、どちらの項が支配的かを述べてください。二分ヒープを使ったダイクストラ法はO((V + E) log V)で、BFSはO(V + E)です。動的計画法ではテーブルのサイズを数えてください:長さmとnの二つの文字列ならm×nのテーブルになり、二行だけ保持すれば空間はO(min(m, n))に減ります。