# Could I apply the master theorem if my $N/b$ is $\varphi(N)$?

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.)

You can not apply the master theorem directly. However, you can play with your expression a bit to get an upper bound on which you can then apply the master theorem.

First, show that $$\phi(\phi(n)) < n/2$$. This can be done as such:

Let $$n = \prod_{i=1}^rp_i^{k_i}$$ be the prime factorisation of $$n$$ ($$p_i$$ prime, $$k_i>0$$)

• Suppose $$n$$ is even. Then $$\phi(n) = n\prod_{i=1}^r(1-\frac{1}{p_i}) \leq n(1-\frac{1}{2}) \leq n/2.$$ Thus $$\phi(\phi(n)) < n/2$$.
• Suppose $$n$$ is odd and $$n > 1$$. Then $$\phi(n) = \prod_{i=1}^r (p_i-1)p_i^{k_i-1}$$ is even and smaller than $$n$$. By the previous result $$\phi(\phi(n)) < n/2$$.

So we get the desired result.

Now suppose $$n\geq2$$. You can write: $$T(n) = T(\phi(n))+\log(\phi(n))^3 = T(\phi(\phi(n)))+\log(\phi(\phi(n)))^3 + \log(\phi(n))^3.$$ $$T(n) \leq T(n/2) + 2\log(n)^3.$$

Now you can apply the master theorem here to get: $$T(n) = O(log(n)^4).$$

• Are you sure the answer is $O(\log^4 n)$? Looking at Cormen's book, I understood $a = 2$, $b = 2$ and case 1 applies because $2 \log^3 n \in O(n^{(\log_2 2) - e}) = O(n)$, so the answer would be $\Theta(n^{\log_2 2}) = \Theta(n)$. Where am I wrong? How did you get the 4th power? – R. Chopin Aug 25 '19 at 19:04
• You have a=1 and not 2, so you can use case 2 of the more precise formulation given here : en.wikipedia.org/wiki/Master_theorem_(analysis_of_algorithms). Alternatively, you can just do a prove by induction without using the master theorem, it will yield the same result quite easily. – Tassle Aug 25 '19 at 20:03
• Notice also that because we work on an upper bound of $T$ and not the exact formula, we can no longer deduce lower bounds on the complexity via the master theorem, thus we can only get $T(n)=O(\text{something})$ and no longer $T(n)=\Theta(\text{something})$. – Tassle Aug 25 '19 at 20:09
• Oh I see, no worries :) And yep, $O(n)$ for $a=2$ seems right to me. – Tassle Aug 25 '19 at 21:28
• Oh I'm sorry, I just realized that my upper bound doesn't work out that way any more if $a = 2$. In fact, the new upper bound would be $T(n) \leq 4T(n/2) + ...$, which leads to $O(n^2)$. But regarding your point, yes, in the first case of the master theorem growth can be arbitrarily fast in $F(n)$. Try it out with $F(n) = 0$ and you'll get, hum, infinite growth in $F(n)$, whatever that means – Tassle Aug 25 '19 at 22:14