2
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – R. Chopin Aug 25 at 19:04
  • 1
    $\begingroup$ 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. $\endgroup$ – Tassle Aug 25 at 20:03
  • 1
    $\begingroup$ 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})$. $\endgroup$ – Tassle Aug 25 at 20:09
  • 1
    $\begingroup$ Oh I see, no worries :) And yep, $O(n)$ for $a=2$ seems right to me. $\endgroup$ – Tassle Aug 25 at 21:28
  • 1
    $\begingroup$ 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 $\endgroup$ – Tassle Aug 25 at 22:14

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.