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:
Iterate through 1 to k and calculate each $\gcd$: $O(n \log(n))$
Factor n first and then use Euler’s product formula: $O(n)$
Are there any other possibilities?