IPA公式正解：ウ O(n^2)
※ 正解はIPA公表の解答です。解説は当サイトが生成AIを用いて作成しています。誤りにお気づきの場合はお問い合わせください。
【解説】正解は選択肢【ウ】です。入れ子ループ法（Nested Loop Join）は、外側表の各行に対して内側表の全行を走査して結合条件を比較する手法です。タプル数nの表同士を比較する場合、外側ループでn回、内側ループでn回の走査が発生するため、比較回数はn×nとなり計算量はO(n^2)となります。
【詳細解説】■ 本問の核心・解法のポイント
入れ子ループ法（Nested Loop Join）の基本アルゴリズムと計算量の評価を理解しているかを問う問題です。入れ子ループ法では、一方の表（外部表）の全タプル（n件）を走査しながら、各タプルに対してもう一方の表（内部表）の全タプル（n件）を順次読み出して結合条件を判定します。
インデックスが存在しない場合、外部表の各タプルにつき内部表の全走査が必要となるため、総比較回数は n × n = n^2 回となり、計算量は O(n^2) になります。
・各選択肢の徹底解説：
・ア：O(n) は、1つの表の単純走査（フルテーブルスキャン）などの計算量です。
・イ：O(log n) は、ソート済みデータに対する二分探索やB+木インデックス探索の計算量です。
・ウ：【選択肢ウ★】入れ子ループ法におけるタプル数nの表同士の結合操作の計算量は O(n^2) です。
・エ：O(n log n) は、ソートマージ結合の前処理として行うソート処理や、内部表にB木インデックスが存在する場合の入れ子ループ結合の計算量です。
よって正解はウです。
