# Time complexity of Euler's totient function

I believe there are different time complexities for Euler's totient function depending on how you execute the algorithm. The two I know of are:

1. Iterate through 1 to k and calculate each $$\gcd$$: $$O(n \log(n))$$

2. Factor n first and then use Euler’s product formula: $$O(n)$$

Are there any other possibilities?

• Both formulas are wrong. For the first, there seems to be a mix between $k$ and $n$, and calculating $\gcd(k,n)$ when $0<k<n$ has cost sizably larger than $O(\log n)$. For the second, factoring $n$ has cost much lower than $O(n)$. – fgrieu May 17 '19 at 6:25
• You may want to note that "computing the euler totient function of a number" is (roughly) as difficult as "factoring that number", so don't expect anything better than "factor, then compute". – SEJPM May 17 '19 at 8:36
• Euler's function is not itself an algorithm, and as such does not have a time complexity. When you specify an algorithm, that algorithm will have a time complexity. It depends, of course, on what units of ‘time’ you're counting ($\lg n$-bit multiplications? bit operations? communication costs?), including how much parallelism you can throw at it and what type of machine you have. – Squeamish Ossifrage May 17 '19 at 14:21