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?

  • $\begingroup$ 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)$. $\endgroup$
    – fgrieu
    May 17, 2019 at 6:25
  • 3
    $\begingroup$ 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". $\endgroup$
    – SEJPM
    May 17, 2019 at 8:36
  • $\begingroup$ 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. $\endgroup$ May 17, 2019 at 14:21


Your Answer

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

Browse other questions tagged or ask your own question.