Почему не сложность времени алгоритма Sieve of Eratosthenes имеет аргумент sqrt (n)?

Question

Я пытаюсь понять сложность алгоритма времени решета Эратосфена. Всюду в Интернете говорится, что временная сложность O (nloglog (n)), но я не понимаю, почему.

Вот некоторые псевдокоды

factors = new int[n+1]; 
for i from 2 to n 
    factors[i] = 1; //true 

for i from 2 to sqrt(n) 
    if(factors[i] == 1) //isPrime 
    { 
     for all multiples of i upto n 
      factors[multiple] = 0 //notPrime 
    } 

return all indices of factors that have a value of 1 

Я думаю, что мы все можем согласиться, что временная сложность этой функции зависит от вложенного для цикла. Теперь его анализ. Когда i = 2, внутренний цикл работает n/2 раза. Когда i = 3, внутренний цикл выполняется n/3 раза. В следующий раз, когда выполняются внутренние петли, это следующее простое число, поэтому n/5 раз. В общей сложности цикл будет выполняться

N/2 + п/3 + п/5 + п/7 + ... раз

Это

п (1/2 + 1/3 + 1/5 + 1/7 + ...)

Сумма обратных чисел простых чисел до n является элементом O (log (log (n))). Таким образом, общая сложность - O (nlog (log (n)))

ОДНАКО, как написано в нашем псевдокоде, внешний цикл for запускает только root (n) раз. Таким образом, мы суммируем только обратные числа простых чисел до sqrt (n). Поэтому сложность должна быть O (nlog (log (sqrt (n)))), а не то, что указано выше.

Что не так с моим анализом?

Answer 1

O (nlog (log (sqrt (n)))) is O (nlog (log (n))), поскольку log (sqrt (n)) = log (n)/2.