ユーザ入力を伴うwhileループのためのBig-O

Question

モジュールXがp単位の実行時間を必要とすると仮定します.pは定数です。次の各アルゴリズムの複雑さを求めます.nは入力データのサイズ、qは1より大きい正の整数です。時間の複雑さはどのようになりますか？対数関数の塩基がqある

set i = 1 
    `while i ≤ n` 
     `Module X` 
     `i = q * i` 
    endwhile 

Answer 1

log(n)。

ヒント：iは指数関数的に増加します。