凸包アルゴリズム
明らかに、記述された数値のポイントへの変換と、それらのソートされた順序の抽出には線形時間が必要である。したがって、一般的なケースでは、 凸包はソートよりも速く計算できない。
ソートで標準とされる Ω(n log n)の下限は、決定木モデル内で証明されています。決定木モデルは数値比較のみを実行でき、算術演算は実行できないもので、凸包は算出できない。凸包に適したモデルである代数決定木(英語版)モデルでも、ソートには Ω(n log n)時間が必要であり、このモデルでは凸包にも Ω(n log n)時間が必要である。ただし、たとえば整数のソート(英語版)アルゴリズムを使用して、数値を O(n log n)時間よりも速く並べ替えることができるコンピューター演算のモデルでは、平面凸包もより速く計算できる。例えば、凸包のグラハムスキャン(英語版)アルゴリズムは1回のソートと線形時間の処理で実現される。
上記のように、入力サイズ n の凸包を見つける計算量は、Ω(n log n)を下限とする。ただし、一部の凸包アルゴリズムの計算量は、入力サイズ nと出力サイズ h (凸包上の点の数)の両方で決まる。このようなアルゴリズムは、出力依存アルゴリズム(英語版)と呼ばれる。h = o(n)の場合、これらは、Θ(n log n)アルゴリズムよりも漸近的に効率的と考えられる。
出力依存の凸包アルゴリズムの最悪時間計算量の下限は、平面の場合で Ω(n log h)であることが確立された。この最良の時間計算量を達成するアルゴリズムは複数ある。最初のものは、1986年にカークパトリックとサイデルによって発見された(彼らはそれを「究極の凸包アルゴリズム(英語版)」と呼んだ)。1996年には、さらに単純なアルゴリズム、チャンのアルゴリズム(英語版)がチャンによって開発された。