-1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Which did you try? How close did you get? Have you tried solving the recurrence symbolically in $f$, and then solve for $f$? $\endgroup$ – Raphael Apr 20 '17 at 18:23
  • 3
    $\begingroup$ 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$.) $\endgroup$ – David Richerby Apr 20 '17 at 20:16
1
$\begingroup$

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)}}}}$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Great! Thank you so much for the explanation!! $\endgroup$ – AmR Apr 22 '17 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.