Given the recursive function:($c$ is a constant)$\qquad T(n) = \begin{cases}1 & n  c\\2T(f(n)) + 1 & n > c\end{cases}$I need to find a $f(n)$ such $T(n)  (log^4 n) = (\log \log \log \log n)$.I tried the iteration method, and it gave me $\qquad 2^i*T($$f1$($f2$(...$fi$($n$)..$))) + i $ which revealing the pretty much expected formula for $i$. i know that $f(n) = \sqrt(x)$ would give $log(log(n))$, Is that the right direction? or which function will get closer?Thanks.
Finding f(n) so 2T(f(n)) + 1  (log^4 n)
asymptotics;recurrence relation