基本情報技術者についての質問。 探索アルゴリズムの計算量で、 O(logn)のlognの計算はどのようにして行う…

Question

基本情報技術者についての質問。

探索アルゴリズムの計算量で、
O(logn)のlognの計算はどのようにして行うのですか？
底は何になるのでしょうか？

回答のほどよろしくお願いします。

Answer 1

O(logn)の底は、なんでもいいんですよ。
（基本的にはeでしょうけど）

例えば、
log₂n
を変形してみると、
log₂n=logn/log2=1/log2×logn
となります。
この時、1/log2は「定数」なので、O表記には現れません。
結局、O(logn)になりますよね。