1
$\begingroup$

Code for finding $\phi$(n) is

int phi(int n)
    {    
        int result = n;   // Initialize result as n

        // Consider all prime factors of n and subtract their
        // multiples from result
        for (int p=2; p*p<=n; ++p)
        {
            // Check if p is a prime factor.
            if (n % p == 0)
            {
                // If yes, then update n and result 
                while (n % p == 0)
                    n /= p;
                result -= result / p;
            }
        }

        // If n has a prime factor greater than sqrt(n)
        // (There can be at-most one such prime factor)
        if (n > 1)
            result -= result / n;
        return result;
    }

I don't understand how is the overall complexity $O(\sqrt{n}) $.

From the code, I see that the outer loop runs for $O(\sqrt{n}) $ time but I am not sure of how to include the time complexity of the inner loop for finding the overall complexity.

If we have n=$128$, then outer loop runs for $O(\sqrt{n}) $ time and inner loop for $O(log_2 n)$, so overall complexity is $O(\sqrt{n}) $ + $O(log_2 n)$ which is $O(\sqrt{n}) $.

I don't know how to extend this for general case of $n=P1^{a1}*P2^{a2}*P3^{a3}*..Pn^{an}$

$\endgroup$
1
$\begingroup$

The cost inner loop if $n$ is equal to $P_1^{a_1}P_2^{a_2}\cdots P_k^{a_k}$, should be run in $\log_{P_1}n + \log_{P_2}n + \cdots + \log_{P_k}n$ totaly which is $O(k\log(n))$.Notice that, these computation is computed over the outer loop and summation of all iterations of the outer loop.

To more scrutinizing, as the maximum asymptotic number of primes less than $x$ is $\frac{x}{\log x}$, size of $k$ would be $O(\frac{\sqrt{n}}{\log\sqrt{n}})$. Hence, The complexity of the problem would be: $$O(\sqrt{n} + k\log(n))=O(\sqrt{n} + \frac{\sqrt{n}}{\log\sqrt{n}}\log(n)) = O(\sqrt{n}+\frac{\sqrt{n}}{2})=O(\sqrt{n})$$

$\endgroup$
  • $\begingroup$ @Zephyr Each item of the inner loop runs in $\log_{p_i}n$. The summation of these is meaning besides the outer loop. In the other words, each item of the sum happened in each iteration of the outer loop. $\endgroup$ – OmG Mar 4 '18 at 16:58
0
$\begingroup$

Whenever you find a factor, n gets smaller. The amount of work needed to process one factor is trivial compared to the savings you get by dividing n by that factor.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.