元素相異性下界（element-distinctness lower bound）

元素相異性問一個簡單的是非問題：給定 n 個數，它們是否兩兩不同，還是有某個值重複了？你可以用排序（n log n）後掃描相鄰元素，或用雜湊（期望線性）來解。元素相異性下界證明：在一個自然的模型中——你透過算術與比較操弄這些數——你無法可靠地打破 Omega(n log n)，乾淨的線性時間答案在那裡不可能。這一個問題是證明其他幾何與排序相關任務很難的主力。

這個界活在代數決策樹模型中，那裡每一步計算輸入的一個多項式，並依其正負號（正、零、負）分支，推廣了單純的比較。證明的想法出自 Ben-Or，是幾何的。把一筆輸入想成 n 維空間中的一個點。「全相異」的輸入構成一個區域，而那個區域被打碎成極多互不相連的碎片——大約 n! 片，對應 n 個值的每一種順序，因為要從一種順序移動到另一種，你必須經過一個有兩個座標相等的點（一筆「不相異」的輸入）。一棵樹高為 h 的決策樹，最多把空間切成有界數目的碎片，其數目像某常數的 h 次方那樣成長。因此要分開 n! 個連通碎片，你需要樹高 h = Omega(log(n!)) = Omega(n log n)。是「互不相連的連通分量」的幾何逼出了這個深度。

誠實的範圍。此界針對代數決策樹模型，且是最壞情況的陳述；它「不」適用於跳脫它的模型。雜湊在期望 O(n) 內解元素相異性，因為雜湊用整數數值去索引一張表，而非只用多項式的正負號——所以它不是反例，它在模型之外。這個界之所以如此重要，在於槓桿：許多問題歸約到或自元素相異性——最近點對、判斷是否有任意三點共線、某些集合問題——所以它的 Omega(n log n) 地板可藉由歸約轉移給它們，使它成為計算幾何中最常被重複使用的下界之一。