Could I apply the master theorem if my $N/b$ is $\varphi(N)$?
-
05-11-2019 - |
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