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, 2017 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$ Apr 26, 2017 at 12:23
  • 1
    $\begingroup$ Possible duplicate of algorithm time analysis "input size" vs "input elements" $\endgroup$ Apr 26, 2017 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$ Apr 26, 2017 at 21:22

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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