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

  • $\begingroup$ +1 for phi(phi(N)) < N/2 alone. $\endgroup$
    – 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.


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.