CODEWITHSUNDEEP
c++time-complexity
Asad5059
Asad5059

Reputation: 13

Time Complexity Analysis of a function

What is the time complexity of this following function? I am confused between O(log n) and O(sqrt(n)).

map<long long int,long long int> mp;
void PrimeFactorization(long long n)
{
    while(n%2==0)
    {
        n/=2;
        mp[2]++;
    }
    for(long long int i=3;i<=sqrt(n)+1;i+=2)
    {
        while(n%i==0)
        {
            n/=i;
            mp[i]++;
        }
    }
    if(n>2)
    {
        mp[n]++;
    }
}

Upvotes: 1

Views: 329

Answers (1)

Jacob Steinebronn
Jacob Steinebronn

Reputation: 863

This runs in O(sqrt(n)). Technically, it's O(sqrt(n) + log(n)log(log(n))), but that log factor isn't really that big of a deal (and you can get rid of it by using an unordered map).

Think of the worst case: If n is prime, then the loop from 3 up to sqrt(n) will just spin all the way up to its limit. This isn't even much of an edge case, since primes are fairly common. Really, the loop is just searching for all the prime factors of n anyway, so it will have to go up to sqrt(n) because that's the limit of the prime factors.

There are other, much faster prime factorization algorithms. Check out https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes and https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test

Upvotes: 1

Related Questions