ソート
ソートを行う際、要素間の順序の決定を2要素の大小関係の比較処理のみを用いて行うことにする。この時、 n {\displaystyle n} 要素からなるリストをソートするアルゴリズムの最悪比較回数は Ω ( n log  n ) {\displaystyle \Omega (n\log n)} 回となる。すなわち、どんな比較ソートアルゴリズムであっても入力によっては(一般的な入力に対しては)漸近的に n log  n {\displaystyle n\log n} 回の比較が必要となる。
この理由を説明する。ある比較ソートアルゴリズムが与えられた際、様々な入力に対する処理の手順を二分決定木として表すことができる。内部ノードは2要素の比較処理を表し、内部ノードから子ノードへの2本の枝は比較結果に応じた処理を表す。また、葉は処理の終了を表す。この時、木の高さが最悪比較回数となる。 n {\displaystyle n} 要素からなるリストが入力される時、どのような二分決定木を作ったとしても、木の高さが Ω ( n log  n ) {\displaystyle \Omega (n\log n)} になることを示す。