線形時間
ハードウェアの場合、標準的な計算モデルでは線形時間を達成できないアルゴリズムも線形時間にすることが可能な場合がある。例えば、問題の並列性を応用したハードウェア技術などがあり、連想メモリがその1つである。
例えばソートアルゴリズムは、入力となる要素列によっては線形時間でソートを完了するものもあるが、要素同士の比較に基づいたソートアルゴリズムでは一般に O(n log n) より時間を短縮できない。このような複雑性の下限の証明はΩ記法の対象であり、一般的ソートアルゴリズムは Ω(n log n) と言える。同様に無作為な要素列から最大値を探す選択アルゴリズムは、最大値を求めるのに少なくとも (n - 1) 回の比較が必要であることが論理的に示され、Ω(n) となる。
入力全体を見ないと結果が得られない問題は、入力を全て読み込むだけでも線形時間かかるため、少なくとも線形時間以上かかる。