I am having trouble finding the solution to this interview-like question:

$T(n)$ is given as:

$$T(n) = \begin{cases} 1 & n \leq c, \\ 2T(f(n))+1 & n > c, \end{cases}$$

where $c$ is some constant.

Find a function $f(n)$ so that $T(n) = \Theta(\log\log\log\log n)$.

  • $\begingroup$ I'm definitely not sure, but $n/32-1$ gets rid of the +1 and the *2, and then divides the number by 16 for the $loglogloglog$, $\endgroup$ – Ben I. Apr 26 '17 at 10:37
  • $\begingroup$ In your title, the expression $\log^4n$ is generally taken to mean $(\log n)^4$, rather than $\log \log \log \log n$. $\endgroup$ – Rick Decker Apr 26 '17 at 12:23
  • 1
    $\begingroup$ Possible duplicate of algorithm time analysis "input size" vs "input elements" $\endgroup$ – David Richerby Apr 26 '17 at 21:21
  • $\begingroup$ @RickDecker Funny. This is an exact duplicate of another question, and that person also assumed tha $\log^kn$ means $k$-times-iterated log rather than log-raised-to-the-power-$k$. $\endgroup$ – David Richerby Apr 26 '17 at 21:22

I'm solving the case where $c=1$. Doing it for arbitrary $c$ is made in a similar fashion.

Let take $f(N) = 2^{2^{2^{\sqrt{\frac{\log^{[3]} N}{2}}}}}$. so that for every integer $N$ we have : $$T\left(2^{2^{2^N}}\right) = 2 T\left(f\left(2^{2^{2^N}}\right)\right)+1 = 2 T\left( 2^{2^{2^\sqrt{N/2}}} \right)+1.$$

I'm assuming in your question that you are only interested in functions $f$ that are increasing over $\mathbf{N}$. Let prove that $T(N) = \Theta(\log^{[4]} N)$, that is proving that there exists two positive constants $A,B$ such that for sufficiently big $N$, $$ A\log N \leq T\left(2^{2^{2^{N}}}\right) \leq B\log N.$$

Let assume the last inequality holds up to some $\sqrt{N}>1$, with constant $A=1$ and some $B > 1$. Then $$f\left(2^{2^{2^N}}\right) = 2 T\left( 2^{2^{2^\sqrt{N-1}}} \right)+1,$$ and so by hypothesis: $$\log N = 2 \log\sqrt{N/2} +1 \leq T\left(2^{2^{2^N}}\right) \leq 2 B\log\sqrt{N/2}+1 = B \log N +1-B \leq B\log N.$$

We can then conclude by induction, jumping by successive squaring, using the increasing property of $T$ to fill the gaps.

| cite | improve this answer | |

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.