N % K
が 前章のプログラムで何回程度実行されるか考えてみよう.
このプログラムが最悪の動作をするのは, N が素数の時である.
N が素数の時には, K は N に達するまで 1 づつ増え
つづける.
したがって, N 回余りの計算が実行される.
よって N の 2 進数であらわした桁数を とすると,
回程度の余りの計算が実行されることになる.
ここで は -記法とよばれ, が十分大きい時, 程度の大きさ であるような数をあらわす. ここで は定数である. 例えば, , である.
プログラムやアルゴリズムの実行時間やメモリ使用量を 入力データサイズの関数で評価することを計算量の評価という. 実行時間(時間計算量)を調べるには, 一番多く実行される文の実行回数を目安にすると よいであろう.
たとえば, 上のプログラム prime_factorization(N) の 場合は N に素数をいれた場合, ループが O(N) 回実行される. したがって次のような定理がなりたつのはほぼ明らかであろう.
アルゴリズムの性能表示は など -記法を利用しておこなわれる. がどの程度違うか 表にしてみてみよう. ここで は を底とする の対数である.