Вот функция разложения на простые множители:
function primeFactors(n){
// Print the number of 2s that divide n
while (n % 2 == 0) {
console.log(2);
n = n/2;
}
// n must be odd at this point. So we can skip one element
// (Note i = i +2)
for (var i = 3; i * i <= n; i = i + 2) {
// While i divides n, print i and divide n
while (n % i == 0) {
console.log(i);
n = n / i;
}
}
// This condition is to handle the case when n is a prime number
// greater than 2
if (n > 2) {
console.log(n);
}
}
Автор книги считает, что временная сложность алгоритма равна O(sqrt(N)). Но while цикл, который внутри цикла for имеет сам сложность log n, тоже самое показывает wiki - Перебор делителей. Там написано . Подскажите, пожалуйста, как всё таки правильно и почему? Книга - JavaScript Data Structures and Algorithms, 3-я глава.