Theta runtime из 2 логарифмических вложенных для петель

Question

Какая версия времени для Theta имеет следующий код?

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

Я пришел с этим: Т (п) = журнала (п) * (1 + журнал (п)) = журнал (п) + журнал^2 (п), и теперь я не знаю, что положить в обозначение Тета?

Answer 1

log (n) + log^2 (n) = Theta (log^2 (n)). Вам просто нужно взять доминирующий термин. Чтобы убедиться в этом, вы можете написать

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

, которая достаточна, чтобы доказать, что Т (п) Theta (срубы^2 (п)).