O(log N)の底は何なのか

アルゴリズムの計算量を評価するときに、O記法がよく用いられます。
O(log N)は、Nが十分に大きければ、その関数はlog Nに比例するということを意味します。

ところで、このlogの底は何なんでしょうか？

答え

気にしなくても良い。

対数の底の変換公式を使うと、以下のように変形できるので、底については気にしなくても良いです。

\begin{align}
\log _a b &= \frac{1}{\log a} \times \log b \\
          &= O(\log b)
\end{align}