Question

Let

$$T(N) = \begin{cases}1 & \text{if } N = 1\\ T(\varphi(N)) + \lg(\varphi(N))^3 & \text{otherwise} \end{cases}$$

where $\varphi(N)$ is Euler's totient function.

Can I somehow express $\varphi(N)$ as $N/b$, so I can apply the Master Theorem and resolve this recurrence?

You may assume $\varphi(N) = (p-1)(q-1)$, if it's easier that way. You may also assume, if it helps, that $p$, $q$ are safe primes, that is, $p = 2p' + 1$ and $q = 2q' + 1$. (Assume anything that makes the problem easier. For instance, you can replace the function $\lg^3(\varphi(N))$ with any other that makes the problem easier, but do so only as a last resort.)

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top