2 대수의 Theta 런타임은 루프에 중첩됩니다.

Question

Theta 런타임에는 다음 코드가 있습니까?

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

나는이 함께했다 : T (N) = (n)이 로그 * (n은 1 + 로그()) = (n)이 로그 +^2 (N)를 기록하고 지금은 모른다 Theta 표기법에 무엇을 넣어야합니까?

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))임을 증명하기에 충분합니다.