以下の擬似コードに対して正確かつ漸近的な答えを与える

Question

for i <--- 1 step i <--- 2* i while i< n do 
    for j <--- 1 step j <---2* j while j<n do 
    if j = 2*i 
     for k = 0 step k <--- k+ 1 while k < n do 
     .... CONSTANT NUMBER OF ELEMENTARY OPERATIONS 
     end for 
    else 
     for k<--- 1 step k<-- 3*k while k<n do 
     ...CONSTANT NUBER OF ELEMENTARY OPERATIONS 
     end for 
    end if 
    end for 
end for 

nの関数として次のコード断片の実行時間はどれくらいですか？

「正確な答え」は、漸近的な実行時間を決定する前に、コードに関する式を参照しています。

Answer 1

しかし、いくつかの点を考慮すると、擬似コードの漸近的複雑さはO(n*log(n))でなければなりません。

システムによって大きく異なるため、実行時間を正確に予測することはできません。