Как T (n) кода O (nlog (n))?

Question

Я не получаю часть, где T (n) второго цикла цикла - log (n). Обе петли связаны i, и это запутывает. Как T (n) кода O (nlog (n)) с использованием фундаментального правила продукта?

for(i = 1; i <= n; i++) 
{ 
    for(j = 1; j <= n; j = j + i) 
    { 
     printf("Hi"); 
    } 
} 

Answer 1

Для i=1 внутренний цикл выполняется n раз. Для i=2 внутренний цикл выполняет n/2 раз и так далее. Время работы T(n) = n + n/2 + n/3 + ... + n/n. Это равно n(1 + 1/2 + 1/3 + ...+ 1/n) = nH(n), где H(n) - номер n-й гармоники. H(n) ~ lg n, следовательно, время работы O(n lg n).

Answer 2

for(i = 1; i <= n; i++) // Executes n times 
{  
    for(j = 1; j <= n; j = j + i) 
    { // This loop executes j times with j increases by rate of i 
     printf(“Hi”); 
    } 
} 

Внутренний цикл выполняется n/i раз для каждого значения i. Его продолжительность составляет nxSum(n/i) для всех i в [1, п]

=>O(nlogn)