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

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.

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.

• +1 for phi(phi(N)) < N/2 alone. – gnasher729 Aug 27 '19 at 19:27

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.