2个对数嵌套for循环的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）=的log（n）*（1点+的log（n））=的log（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））。