# Finding a function f(n) which will bring T(n) runtime to O(log^4(n)) (Interview question)

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

• 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$, – Ben I. Apr 26 '17 at 10:37
• In your title, the expression $\log^4n$ is generally taken to mean $(\log n)^4$, rather than $\log \log \log \log n$. – Rick Decker Apr 26 '17 at 12:23
• Possible duplicate of algorithm time analysis "input size" vs "input elements" – David Richerby Apr 26 '17 at 21:21
• @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$. – David Richerby Apr 26 '17 at 21:22

## 1 Answer

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.