すべての複雑性クラスは曲線を描く
コストを入力サイズに対してプロット
x軸に入力サイズNを、y軸にコスト（操作回数、時間）を置く。各複雑性クラスは異なる曲線を生成する。アルゴリズムの成長率はパフォーマンス曲線の形から認識できる。
O(1) — 平坦な水平線。 関数f(N) = 1。勾配なし。コストはNに関わらず変わることはない。ハッシュテーブル検索：テーブルが10個か10,000,000個の要素を保持しているかに関わらず、1つのハッシュ計算が正しいバケットにジャンプする。
O(log N) — ゆるい上向き曲線、勾配が減少。 N = 1,000,000のとき：コスト ≈ 20操作。曲線は小さなNで急上昇し、その後平坦になる。Nが2倍になるたびに、コストは正確に1単位増加する。
O(N) — 対角斜線。 勾配 = 1（漸近的な意味で）。コストはNと同じ速度で増加する。NがN 3倍増加すれば、コストは3倍になる。
O(N log N) — より急な対角線、わずかな上向き曲率。 O(N)より上、O(N²)より下に位置する。対数因子は線形勾配に緩やかに増加する乗数を加える。
O(N²) — 上向きに開く放物線。 勾配はNが増加するにつれて増加する。N = 10のとき：コスト = 100。N = 100のとき：コスト = 10,000。N = 1,000のとき：コスト = 1,000,000。
増加するギャップ
比率O(N²) / O(N) = N。放物線と対角線の間のギャップはNが増加するにつれて広がる。N = 10のとき：10倍のギャップ。N = 100のとき：100倍のギャップ。N = 1,000のとき：1,000倍のギャップ。N = 50,000のとき：50,000倍のギャップ。ギャップは常にNに等しい。
スケールギャップの計算
大規模な依存性グラフには50,000個のパッケージが含まれている（N = 50,000）。1つのアルゴリズムはO(N)時間で実行される。2番目のアルゴリズムはO(N²)で実行される。このNでは、比率O(N²)/O(N) = N = 50,000。
線分の二等分
繰り返される二等分としての二分探索
N個の要素の整列配列は長さNの線分を形成する。二分探索はこの線分を繰り返し二等分する：
1. 残りの線分の中点を指す。
2. ターゲット < 中点：右半分が消える。左半分で再帰。
3. ターゲット > 中点：左半分が消える。右半分で再帰。
4. ターゲット = 中点：完了。
k回の二等分後、残りの線分の長さはN / 2^k。探索は長さが1になるまで続く：
N / 2^k = 1 → 2^k = N → k = log₂N
したがって、N個の要素に対する二分探索は最大log₂N回の比較が必要。
半分割と倍増：同じ曲線の両側
半分割と倍増は幾何学的な逆数である。指数曲線2^kと対数曲線log₂Nは、直線y = xの両側で反射している。
紙を折ることを考える：用紙は0.1 mmの厚さから始まる。折るたびに厚さが2倍になる。42回の折り目の後：0.1 mm × 2^42 ≈ 439,804 km — 月を過ぎている（384,400 km）。二分探索は逆を実行：N個の要素から開始し、各ステップで数を半分にし、log₂Nステップで1要素に到達する。
幾何学的：二等分は自己相似操作である。各二等分は全体と同じ構造を見た2つの半分を生成する。再帰と対数はこの自己相似性を共有する。
比較と倍増
整列配列は1,048,576個の要素を含んでいる。注意：1,048,576 = 2^20。
幾何学的マップとしてのハッシュ関数
関数としてのハッシュ関数
ハッシュテーブルはハッシュ関数を使用してキーをバケットにマッピング：
bucket = hash(key) mod table_size
これは厳密な数学的意味での関数：定義域（可能なすべてのキー）を値域（バケットインデックス0からtable_size−1）にマッピング。幾何学的イメージ：キーは1つの空間に存在；バケットは別の空間に存在。ハッシュ関数はキーをバケットインデックスに投影する。
O(1)検索—直接ジャンプ、検索なし。 ハッシュ関数は一定時間でバケットインデックスを計算する。そのバケットに直接ジャンプ。トラバーサルなし、比較ループなし。
負荷係数。 負荷係数0.75では、75%のバケットが少なくとも1つの要素を含む。約0.9を超えると、衝突が増加：2つのキーが同じバケットにハッシュされ、そのバケット内に要素のチェーンを形成。長いチェーンでの検索は最悪の場合O(N)に低下。
分布品質としての幾何学
よく分散されたハッシュ関数はキーをすべてのバケットに均一に分散。幾何学的：関数の値域がその余域を均等にカバー。各バケットはおよそN / table_sizeのキーを受け取る。
悪いハッシュ関数はキーをいくつかのバケットにクラスター。幾何学的：関数の値域は余域のサブセットに折りたたまれる — ほとんどのキーは同じ数個の点にマップ。残りのバケットは空のまま。
MOAD-0001との接続
リストをセットで置き換えるとMOAD-0001を修正する。なぜなら、セットは内部的にハッシュテーブルを使用するため。O(N)リストスキャン→O(1)ハッシュテーブル検索。幾何学的：シーケンスに沿った線形トラバーサルが関数を介した直接投影に変換。シーケンスは消える；関数がそれを置き換える。
不均一に分散されたハッシュの分析
ハッシュテーブルには1,000個のバケットと900個の要素がある（負荷係数0.9）。悪いハッシュ関数は、これらの要素の500個を同じバケットに送信。