循環的漸近運行時間

Question

function func5(n) 
    s = 0; 
    for i = 1 to 3n^2 do 
    for j = 1 to floor(2n^3/i) do 
    s=s + i − j; 
    return(s); 

上述算法在theta符號中的漸近運行時間是多少？

Answer 1

的總和來表達這一點：

的求和項是調和級數。從Wikipedia page它可被近似爲：

凡gamma是歐拉Mascheroni常數（〜0.577）。因此整體複雜度爲：