What's an upper bound for this recurrence so I can take advantage of the Master Theorem?
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&gt;2$, $\phi(\phi(N)) &lt; 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&gt;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)) &lt; N/2$.
Suppose $N$ is odd and $N &gt; 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)) &lt; N/2$.


So we get the desired result.



Now, let $k&gt;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 &gt; 0$ there exists some $k&gt;0$ such that $p_0 &lt; \epsilon$. So let's pick any $\epsilon &gt; 0$ and set $k$ such that $p_0 &lt; \epsilon$. Plugging that into the last result we get:

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

And this is true for any $\epsilon&gt;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.