実行時間のオーダーの表記法

関数fがあったときに、

すべての場合において、入力のサイズnに比例して実行時間が変化する場合
実行時間は

f(n) = Θ(n)

と表される。

入力の中身によってはオーダーに差がでるとき、
これ以上は実行時間が大きくならないオーダーがnであれば

f(n) = Ω(n)

と表し、
これ以上は実行時間が小さくならないオーダーがnであれば

f(n) = O(n)

と表す。