# Finding f(n) so 2T(f(n)) + 1 ∈ Θ(log^4 n)

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.

• Which did you try? How close did you get? Have you tried solving the recurrence symbolically in $f$, and then solve for $f$? – Raphael Apr 20 '17 at 18:23
• Note that $\log^4n$ almost always means $(\log n)^4$ and not $\log\log\log\log n$. (By analogy with trigonometry, where $\sin^2 x$ never means $\sin\sin x$.) – David Richerby Apr 20 '17 at 20:16

So $T(n)$ goes through the sequence 1, 3, 7, 15, 31, ... We want $T(n) = \Theta (\log \log \log \log n)$; I'll assume log n is the base 2 logarithm. We'll try to define f (n) so that T(n) = log log log log n, rounded up to the nearest element of the sequence 1, 3, 7, 15, 31...
1 < log log log log n ≤ 3 if 2 < log log log n ≤ 8 or 4 < log log n ≤ 256 or 16 < log n ≤ $2^{256}$ or 65,536 < n ≤ $2^{2^{256}}$. So in that range we have T (n) = 3, and c = 65,536. BTW. The upper end of that range is so large that all the paper in the universe wouldn't be large enough to write it down as a decimal number.
Next we look for a range where 3 < log log log log n ≤ 7. That happens when n > $2^{2^{256}}$ and log log log log n ≤ 7 or log log log n ≤ 128 or log log n ≤ $2^{128}$ or log n ≤ $2^{2^{128}}$ or n ≤ $2^{2^{2^{128}}}$, and the numbers involved get quite big.
In the range $2^{2^{256}}$ < n ≤ $2^{2^{2^{128}}}$ we want 65536 < f (n) ≤ $2^{2^{256}}$. f (n) should map $2^{2^{2^{2^{2k+1}}}}$ to $2^{2^{2^{2^k}}}$.
To achieve this, let $g (n) = \log \log \log \log n$, $h (n) = (g (n) - 1)/2$, $f (n) = 2^{2^{2^{2^{h(n)}}}}$.