What is a good bound on this recursion?

Question

$\alpha\in[0,1]$ with $T(N)=2(\log N)^\alpha N^{1/k}T(N^{1-1/k})$ with $T(m)=1$ if $m<2$ and $N\in\mathbb R$. Is there good asymptotics on $T(N)$?

Answer 1

I assume that $k\ne 0$ is constant and the recurrence holds for $N\ge 2$. If $\beta=1-1/k<0$ then $N^{1-1/k}<0$ so $T(N)=2(\log N)N^{1/k}$. So farther I assume that $0<\beta<1$ and $\gamma=\beta^{-1}$. Given $N>2$, choose the smallest natural $s$ such that $N^{\beta^s}<2$. The last inequality is equivalent to $\beta^s\log_2 N<1$, that is $\log_2 N<\beta^{-s}$ and $t=\log_{\beta^{-1}}\log_2 N<s$, so $s-1\le t<s$. We have $1/k=1-\beta$ and

$$T(N)=2(\log N)^\alpha N^{1-\beta}T(N^\beta)=$$ $$2(\log N)^\alpha N^{1-\beta} 2(\log N^\beta)^\alpha N^{\beta(1-\beta)} T(N^{\beta^2})=$$ $$2^2(\log N)^{2\alpha} N^{1-\beta^2}\beta^\alpha T(N^{\beta^2})=\dots=$$ $$2^s(\log N)^{s\alpha} N^{1-\beta^s}\beta^{\alpha(1 +2+\dots+(s-1))}T(N^{\beta^s})=$$ $$2^s(\log N)^{s\alpha} N^{1-\beta^s}\beta^{\alpha s(s-1)/2}.$$

Thus $$2^t(\log N)^{t\alpha}N\cdot 2^{-1}(\log_2 N)^{-\alpha s/2}< T(N)< 2^{t+1}(\log N)^{(t+1)\alpha} N(\log_2 N)^{\alpha (1-s)/2} $$

$$2^{t-1}(\log N)^{t\alpha}N(\log_2 N)^{-\alpha (t+1)/2}< T(N)< 2^{t+1}(\log N)^{(t+1)\alpha} N(\log_2 N)^{\alpha (1-t)/2} $$

Since $x^t=x^{\log_{\beta^{-1}}\log_2 N }=(\log_ 2 N)^{\log_\gamma x}$ for $x>0$, we have

$$2^{-1}N(\log_ 2 N)^{\log_\gamma 2+\alpha\log_\gamma \log N-\alpha/2-(\alpha/2) \log_\gamma\log_2 N}< T(N)<2N (\log_ 2 N)^{\log_\gamma 2+\alpha\log_\gamma\log N +\alpha/2-(\alpha/2)\log_\gamma\log_2 N} (\log N)^{\alpha}$$

Assuming $\log=\log_e$, we have $\log N=\frac {\log_2 N}{\log_2 e}$ and

$$2^{-1}N(\log_ 2 N)^{ (\alpha/2)\log_\gamma\log_2 N+\log_\gamma 2- \alpha\log_\gamma \log_2 e-\alpha/2}< T(N)<2N (\log_ 2 N)^{ (\alpha/2)\log_\gamma\log_2 N+\log_\gamma 2 - \alpha\log_\gamma \log_2 e +3\alpha/2} (\log_2 e)^{-\alpha}.$$