vaibhavmisra's blog

Trial division factorization complexity
By vaibhavmisra, history, 22 months ago, In English

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;
}
  • Vote: I like it
  • -9
  • Vote: I do not like it

Comments Comments (5)
| Write comment?
»
22 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

It is O(sqrt(n)) actually, considering the case when n is a prime number.

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The number of prime factors will always be less than √n, So TC = O(√n)

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    do we have any proof of that?

    → Reply
    • »
      »
      »
      22 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply