How to solve this recursion?

53 Views Asked by At

If $r>0$ holds and recursion is given by $T(r)=\alpha T(r^{1/\alpha})+\alpha r^{1/\alpha}$ where $\alpha\geq 2$ is fixed and assume $T(r)=O(1)$ for $r\leq1$.

What is $T(r)$?

1

There are 1 best solutions below

1
On

I've got a feeling that evaluating $T(N)$ at $N = 1$, then proceeds to express $T(N)$ as a summation of $\alpha ^k . N^\frac{1}{\alpha ^{k+1}}$ and $\alpha . T(N^\frac{1}{\alpha ^{n+2}})$ where $n$ is the number of terms, then taking limit to infinity will help