ランダウの記号

例としては、以下のようなものがあります。

以下の例はすべて Python で書かれたコードを使用しています。これは Big O 型の完全なリストではないことに注意してください。

定数

O ( 1) {displaystyle O(1)} .入力に関係なく、常に同じ時間がかかる。例えば、整数（xと呼ばれる）を受け取って、その値の２倍の値を返す関数を考える。

この関数は、入力を受け付けた後、必ず１ステップで出力を返す。常に同じ時間がかかるので定数なので、O ( 1 ) {\displaystyle O(1)} .

リニア

O ( n ) {displaystyle O(n)} .n {displaystyle n}で表される入力の大きさに応じて増加する。ある関数がnを受け入れて、1からnまでのすべての数を返すとしよう。

5の値を入力すると、1, 2, 3, 4, 5 {\displaystyle 1,2,3,4,5}が出力されます。を出力します。同様に、100と入力すると、1,2,3...98,99,100 {\displaystyle 1,2,3...98,99,100}と出力され、100ループを完了する必要がある。入力がn {\displaystyle n}ならば、アルゴリズムの実行時間は毎回正確にn {\displaystyle n}ループするので、O ( n ) {\displaystyle O(n)} .

要因

O ( n ! ) {displaystyle O(n ! ) } .乗的に増加し、入力に伴って時間が大幅に増加することを意味する。例えば、世界の5つの都市を訪問して、可能な限りの順序（順列）を見たいとします。Pythonのitertoolsライブラリを使って書けるアルゴリズムは以下の通りです。

このアルゴリズムは、各都市のユニークな順列を計算して出力します。出力の例としては、以下のようなものがあります。

('London', 'Paris', 'Berlin', 'Amsterdam', 'Rome', 'Amsterdam') ('London', 'Paris', 'Amsterdam', 'Berlin', 'Rome', 'Amsterdam') ...('Rome', 'Amsterdam', 'Paris', 'Berlin', 'London') ('Rome', 'Amsterdam', 'Berlin', 'London', 'Paris') ('Rome', 'Amsterdam', 'Berlin', 'Paris', 'London')

ここでは、入力リストは5つの項目で、選択するごとに残りの選択肢が1ずつ減っていく。 つまり、5つの入力は、5×4×3×2×1 {\displaystyle 5 4times 4Times 3\times 2Times 1}の項目を選択する（または、5 !入力がn {displaystyle n} Cities longならば、出力数はn !つまり、すべての順列を通るとすると、それを完成させるには、O ( n ! ) {\displaystyle O(n ! ) }のループが必要になる。

リトルオー記法

Big Oのより厳格なバージョンがlittle-oである。big Oとlittle-oの違いは、little-oが厳密な上限であることである。O ( n ) {\displaystyle O(n)}が入力サイズに基づいて完了時間がこの最大値まで増加することを意味するのに対し、o ( n ) {\displaystyle o(n)}は完了時間が一般的にこの時間以下になることを意味する。言い換えれば、Big Oはすべてのループが最も長いパスを取り、プロセスが可能な限り長くかかると仮定するのに対し、little-oは実際の実行時間についてより現実的である。ループの数が6面のサイコロを振ることに基づいている場合、Big Oは常に6が振られると仮定するのに対し、little-oは他の数字が振られる確率が等しいことを考慮する。