二進対数
ここで、1以外の任意の正の数 k に対して log2 n = logk n / logk 2(底の変換)が成り立つので、O(log2 n) の実行時間をもつアルゴリズムは、1より大きな任意の底、たとえば13を用いて、O(log13 n) の実行時間を持つとも表現できる。したがって、O(log n) や O(n log n) といった式では、対数の底がいくつであるかは本質的な問題ではない。
ただし、対数の底を指定する必要があるケースもあるので注意が必要である。例えば、所要時間 O(2) の計算と、所要時間 O(2) の計算とは同等ではない。前者は O(n) と等価であり、後者は O(n) と等価である。
O(n log n) の実行時間をもつアルゴリズムは、しばしば線形対数と呼ばれる。O(log n) や O(n log n) の実行時間をもつアルゴリズムの例としては、次のようなものがある。
クイックソート(ただしこれは平均の場合であり、最悪の場合には O(n) となる。)
2分探索木
マージソート
モンジュ配列(英語版)の計算
一般の正の実数に対しては、二進対数は次の2段階の手順で計算できる。
整数部分 ⌊ lb x ⌋ {\displaystyle \lfloor \operatorname {lb} \,x\rfloor } を計算する。
小数部分を計算する。
まず、整数部分の計算は簡単である。任意の正の実数 x に対して、2 ≦ x < 2 となるような整数 n が唯一に定まる。この各辺を 2 で割った 1 ≦ x/2 < 2 という式を立ててもよい。これをもって、二進対数の整数部分を n と定める。そして、この n を使って、小数部分を lb (x/2) と表記することにする。すなわち、y = x/2 と置くと、次のようになる。
lb x = n + lb y ただし、1 ≦ y < 2
小数部分 lb y は、掛け算と割り算のみを使って再帰的に計算できる。この計算手順は以下のとおりとなる。
まず、1 ≦ y < 2 から出発する。y = 1 ならば、小数部分は0となって、その時点で終了である。
y > 1 ならば、y を繰り返し2乗して、2 ≦ z < 4 なる実数 z を得る。2乗した回数を m とすると、 z = y ( 2 m ) {\displaystyle z=y^{(2^{m})}} となる。
この式の両辺の対数をとり、式変形を行うと次のようになる。
ある時点で y = 1 となった場合には、この計算は当然、そこまでで終了する。逆に、永久に y = 1 とならない場合には、この式は無限級数となるが、すべての i について m[i] ≧ 1 が成り立つので、どの項もその直前の項より小さくなっている。よって、比較判定法により、この級数が必ず収束するということがわかる。
実用上は、計算に無限の時間を費やすわけにはいかないので、計算を途中で打ち切った近似値を使うことになる。級数の i 番目の項より後ろを切り捨てた場合の誤差の上限は、(1/2) である。
しかし実際には幸いなことに、このような高コストな計算も、無限級数の切り捨ても必要とせずに、
値を2乗する。
結果が2以上であれば、2で割る。
という計算を繰り返すのみで簡単に対数を得ることができる。具体的なコードを Microsoft Visual Basic で記述すると、下記のとおりとなる。(なお、この実装ではわかりやすさのために、関数の戻り値を2進表現の文字列としてある。当然ながら、その後の計算のためには、何らかの方法で数値型のデータにしなければならない。