アルゴリズム・プログラミング比較問題
線形探索（sequential search）と二分探索（binary search）の平均時間計算量の比較として正しいものはどれか。
A.線形探索はO(log n)、二分探索はO(n)である
✗ 線形探索と二分探索の計算量が逆になっています。線形探索はO(n)、二分探索はO(log n)が正しいです。
B.線形探索はO(n)、二分探索はO(log n)である← 正解
✓ 正解です。線形探索は先頭から順に比較するためO(n)、二分探索は探索範囲を半減し続けるためO(log n)です。
C.線形探索はO(1)、二分探索はO(n log n)である
✗ 線形探索はO(1)ではありません。最良でもO(1)ですが平均・最悪はO(n)です。
D.線形探索も二分探索もともにO(log n)である
✗ 線形探索はO(log n)ではなくO(n)です。二分探索のみO(log n)で動作します。