времени сложность вложенного цикла

Question

Почему временная сложность

function (n) 
{ 
    //this loop executes n times 

    for(i = 1 ; i <= n ; i + +) 
    //this loop executes j times with j increase by the rate of i 
    for(j = 1 ; j <= n ; j+ = i) 
    print(“*”) ; 

} 

время его работы равно п * (п^1/2) = п^3/2

так, O (n^3/2)

Пожалуйста, объясните с помощью математических шагов.

Заранее спасибо.

Answer 1

Время работы ограничено от O(n^{3/2}), но это не туго!

Обратите внимание, что внутренний цикл составляет O(n/i) итераций для каждого i=1,2,...n), поэтому сложность времени составляет O(n * (1 + 1/2 + 1/3 + ... + 1/n)) = O(n log n).

Это потому, что 1+1/2+1/3+...+1/n=O(log n), так как это известный harmonic series.