IPA公式正解：ウ O(n^2)
※ 正解はIPA公表の解答です。解説は当サイトが生成AIを用いて作成しています。誤りにお気づきの場合はお問い合わせください。
【解説】正解は選択肢【ウ】です。入れ子ループ法（Nested Loop Join）では、外側表の各タプル（n件）に対して内側表の全タプル（n件）を走査して突き合わせるため、比較回数は n × n となり、計算量は O(n^2) となります。
【詳細解説】■ 本問の核心・解法のポイント
リレーショナルデータベースにおける代表的な結合アルゴリズム「入れ子ループ法（Nested Loop Join）」の計算量を問う問題です。
入れ子ループ法（インデックスなしの場合）は、外側表（外部表）のタプルを1行ずつ取り出し、それに対応する内側表（内部表）の全タプルを突き合わせて結合条件を判定します。
外側表のタプル数が n、内側表のタプル数が n のとき、二重ループになるため総比較回数は n × n = n^2 となります。したがって計算量は O(n^2) です。
・各選択肢の徹底解説：
・ア：誤り。O(2n) = O(n) は単純な線形走査の計算量です。
・イ：誤り。二分探索やB+木インデックスの単一行検索などの計算量です。
・ウ：【選択肢ウ★】適切。タプル数 n の表同士のNested Loop（インデックスなし）の計算量は O(n × n) = O(n^2) です。
・エ：誤り。ソートマージ結合のソートフェーズや、インデックスを利用した結合などの計算量です。
よって正解はウです。
