例えば、100個の中から、1個を探すのは、全(線形)探索 O(n) しかできない

全データにインデックス・ハッシュがついていれば、O(1)だが、
ソートするには、全探索する必要がある

DB みたいに、B-tree でソートされているのなら、O(log n)

「アルゴリズムと計算量」を勉強して