# Time complexity of euler totient function

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}$

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})$$
• @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. – OmG Mar 4 '18 at 16:58