Solving recurrence relation $T(2n) \leq T(n) + T(n^a)$
Your guess is wrong. In fact, it is not hard to show that assuming $T(n) &gt; 0$ for all $n &gt; 0$, then $T(n) = \Omega(\log^k n)$ for all $k$. Indeed, for this to hold we need that for large enough $n$ we would have
$$
(1+a^k) \log^k n = \log^k n + \log^k n^a \geq \log^k (2n),
$$
or $\sqrt[k]{1+a^k} \log n \geq \log n + \log 2$,
which holds as long as $[\sqrt[k]{1+a^k}-1]\log n \geq \log 2$, and in particular for large enough $n$.

What is the correct order of growth of $T(n)$? To try and find out, write $S(n) = T(2^n)$. The recurrence now becomes
$$ S(n+1) = S(n) + S(an). $$
For large $n$, we would expect $S(n+1) - S(n)$ to be very close to $S'(n)$, and so heuristically we would expect that $S$ satisfy $S'(n) = S(an)$. This equation seems a bit hard to solve, but an approximate solution is $S(n) = n^{\Theta(\log n)}$. Substituting back, we deduce that the order of growth of $T(n)$ should be something like $(\log n)^{\Theta(\log \log n)}$.