c++ - 2 つの対数ネストされた for ループのシータ ランタイム

Question

次のコードを持つ Theta ランタイムはどれですか?

void f(int n)
{
  for(int i=1; i<n; i*=5)
    for(int j=n; j>0; j/=2);
}

私はこれを思いつきました: T(n) = log(n) * (1 + log(n)) = log(n) + log^2(n) そして今、シータ表記に何を入れるべきかわかりません?

Answer 1

log(n) + log^2(n) = Theta(log^2(n))。支配的な用語を取るだけです。これを見るために、あなたは書くことができます

log^2(n) <= log(n) + log^2(n) <= 2*log^2(n)

これは、T(n) が Theta(log^2(n)) であることを証明するのに十分です。