What's an upper bound for this recurrence so I can take advantage of the Master Theorem?

Question

Let

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

where $\varphi(N)$ is Euler's totient function. My objective is to find an upper bound so that I can apply the Master Theorem and find a closed-form formula.

Answer 1

In order to make this answer self-contained, I will repeat the first part of my answer to your other similar question.

---

First, show that for $N>2$, $\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, let $k>2$ be some fixed integer, and suppose $N\geq k^2$. You can write: $$T(N) = T(\phi(N)) + 2T(\sqrt{N})+\lg(\phi(N))^3 $$ $$T(N) = T(\phi(\phi(N))) + 2T(\sqrt{\phi(N)})+\lg(\phi(\phi(N)))^3 + 2T(\sqrt{N})+\lg(\phi(N))^3$$ $$T(N) \leq T(N/2) +4T(N/k) + 2\lg(n)^3.$$ Where we used that $N\geq k^2 \implies T(\sqrt{\phi(N)}) \leq T(\sqrt{N}) \leq T(N/k)$ in the last step.

(Note that I am implicitly assuming $T(n)$ is a monotonically increasing function. One could get rid of that assumption by working on $S(n) = max(T(n),S(n-1))$, at the cost of making the argument more tedious and harder to follow)

---

Now we can apply the Akra-Bazzi method (a generalisation of the master theorem) with:

• $k = 2$
• $a_1 = 1$, $b_1 = \frac12$, $a_2 = 4$, $b_2 = \frac1k$
• $g(x) = 2\lg(x)^3$

First we need to find $p$ such that $a_1b_1^p + a_2b_2^p = 1$, that is: $$(\frac12)^p+4(\frac1k)^p = 1 \;\;\; (*)$$ Let's call $p_0$ the solution to $(*)$.

Then, we need to plug $p = p_0$ into the equation: $$T(N) \in O(N^p(1+\int_1^N\frac{g(u)}{u^p+1}du))$$ To get:

$$T(N) \in O(N^{p_0}(1+\frac{6(N^{p_0}-1)}{p_0^4N^{p_0}\ln(2)^3})) \in O(N^{p_0})$$ (I just trusted WolframAlpha and did some simplifications for the integral, I'm too clumsy/lazy to attempt it myself if I don't have to)

Notice that in $(*)$ we can make $p_0$ arbitrarily close to $0$ by picking a big enough $k$. In other words, for any $\epsilon > 0$ there exists some $k>0$ such that $p_0 < \epsilon$. So let's pick any $\epsilon > 0$ and set $k$ such that $p_0 < \epsilon$. Plugging that into the last result we get:

$$T(N) \in O(N^\epsilon)$$

And this is true for any $\epsilon>0$.

In other words, $T(N)$ grows slower than any polynomial function in $N$.

---

I suspect it is asymptotically not much bigger than $\lg(\phi(N))^4$, as the square root term will vanish pretty fast, but I can't prove anything better than what I showed.

Also note that you could use the master theorem by setting $k=2$ and working on the upper bound $T(N) \leq 5T(N/2) + 2\lg(N)^3$, but this would of course lead to a much weaker result.

Answer 2

What is $\varphi(p)$ when $p$ is prime? Why is this the worst case?

Note that the master theorem is not going to be applicable. It handles subdivision into subproblems whose size is a fixed proportion of the original problem's size: $2T(\sqrt N)$ doesn't fit this model.