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)$?
Asked
Active
Viewed 51 times
0
-
Mmmm since it is a recurrence relation we can suppose $n \in \mathbb{N}$ right ? But $N^{1/\alpha}$ will hardly be an integer, especially if you iterate this "alpha-root" many times. – Zubzub Jul 14 '16 at 08:00
-
I might call that a functional equation, not a recursion. But you should be able to write a recursion equation for $T(N^{1/\alpha^n})$ as a function of $n$. Solve that first, then try to patch the solutions for different $N$ together. Is $T$ assumed to be continuous? – Harald Hanche-Olsen Jul 14 '16 at 08:00
-
@zubzub I never said $N\in\Bbb N$. – Turbo Jul 14 '16 at 08:04
-
@HaraldHanche-Olsen assume $N>0$ and $T$ continuous – Turbo Jul 14 '16 at 08:05
-
I'm might be wrong but I think we should be careful when if we consider $N \geq 1$ because "alpha-rooting" a number many times will make it go to $1$ and the first part of the equation will tend to $\alpha$ and repeat itself infinitely many times since we don't have a bottom-recursion condition. – Zubzub Jul 14 '16 at 08:12
-
Continuity will help. While it is not technically wrong to use $N$ for a real variable, convention dictates that you avoid such usage. Most readers will assume it to be an integer. – Harald Hanche-Olsen Jul 14 '16 at 08:12
-
@HaraldHanche-Olsen $N\rightarrow r$ made – Turbo Jul 14 '16 at 22:56
1 Answers
0
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
-
Yes, but that summation is not easy (as I found out after my first comment on the question). – Harald Hanche-Olsen Jul 14 '16 at 08:23