Hey folks, how the below code from here has O(√n) time complexity? Shouldn't it be equal to the number of prime factors of n?
vector<long long> trial_division1(long long n) {
vector<long long> factorization;
for (long long d = 2; d * d <= n; d++) {
while (n % d == 0) {
factorization.push_back(d);
n /= d;
}
}
if (n > 1)
factorization.push_back(n);
return factorization;
}
why will it be just the number of prime factors? let's say n=2*(big prime number)
you ll need to go to that prime number (or the sqrt of it) , your analysis is not correct.
It is O(sqrt(n)) actually, considering the case when n is a prime number.
The number of prime factors will always be less than √n, So TC = O(√n)
do we have any proof of that?
The upper bound for number of prime factors is log2(n), not even sqrt(n).Imagine the "worst" case: all the prime factors of the number are really small: for example, n = 2^k. Obviously, k <= log(n), otherwise 2^k > n.