CODEWITHSUNDEEP
algorithmtime-complexity
kaid
kaid

Reputation: 1249

run time of this Prime Factor function?

I wrote this prime factorization function, can someone explain the runtime to me? It seems fast to me as it continuously decomposes a number into primes without having to check if the factors are prime and runs from 2 to the number in the worst case.

I know that no functions yet can factor primes in polynomial time. Also, how does the run time relate asymptotically to factoring large primes?

function getPrimeFactors(num) {
    var factors = [];
    for (var i = 2; i <= num; i++) {
        if (num % i === 0) {
            num = num / i;
            factors.push(i);
            i--;
        }
    }
    return factors;
}

Upvotes: 2

Views: 933

Answers (1)

kkonrad
kkonrad

Reputation: 1262

In your example, if num is prime then it would take exactly num - 1 steps. This would mean that the algorithm's runtime is O(num) (where O stands for a pessimistic case). But in case of algorithm that operate on numbers things get a little bit more tricky (thanks for noticing thegreatcontini and Chris)! We always describe complexity as a function of input size. In this case the input is a number num and it is represented with log(num) bits. So the input size is of log(num). Because num = 2 ^ (log(num)) then your algorithm is of complexity O(2^k) where k = log(num) - size of your input.

This is what makes this problem hard - input is very, very small and any polynomial from num leads to exponential algorithm ...

On a side note @rici is right, you need to check only up to sqrt(num), thus easily reducing the runtime to O(sqrt(num)) or more correctly O(sqrt(2) ^ k).

Upvotes: 1

Related Questions