# simple but (seemingly?) tricky recurrence

I'm cross-posting from math stack exchange after receiving no answers there.

I came across the following very simple recurrence-style expression but am having trouble solving it: $$T(2n) \in \theta(T(n) \log(T(n)))$$ for sufficiently large $n \in \mathbb{N}$.

My first thought was to take the logarithm of both sides and apply the Master Theorem but the "$f(n)$" term unfortunately is not in the right form. Repeated expanding quickly yields a mess. Wolfram Alpha was no use.

Plugging in $T(n) = n^a$ makes the left side grow too slowly so $T$ must grow faster than any polynomial. But plugging in $T(n) = \exp(\log(n)^b)$, $b>1$, causes the left side to grow too fast so $T$ must grow more slowly. So it seems $T$ is super-polynomial but barely.

What approaches are viable for such an equation?

• It seems you have figured out a close upper bound, but perhaps you should make it explicit in the question that you want a big-theta characterization. – JimN Dec 25 '17 at 6:32
• T(n) = 2 is a solution :) – gnasher729 Dec 25 '17 at 11:31
• “T(n) = n^a makes the left side grow too slowly”. I can’t see that. I think it will grow too fast if a > 1. – gnasher729 Dec 25 '17 at 11:39
• Please do not post the same question on multiple sites. Each community should have an honest shot at answering without anybody's time being wasted. – D.W. Dec 26 '17 at 17:32
• @D.W. I cross posted because I have seen it done before and it was not badly received. I originally posted to math SE over a month ago and thought the question was relevant to this site as well. I apologize if it's bad etiquette. Should I delete the math SE question, as it is the one that has no answers? – Reinstate Monica Dec 26 '17 at 18:29

Let us attempt to solve the easier recurrence $T(2n) = T(n) \log T(n)$. Define $S(m) = \log T(2^m)$. Then $S(m+1) = S(m) + \log S(m)$. Let us heuristically convert this into a differential equation: $S' = \log S$. The solution to this equation is $S = \mathrm{li}^{-1} + C$, where $\mathrm{li}$ is the logarithmic integral. Roughly speaking, $\mathrm{li}(x) \approx x/\log x$, and so $\mathrm{li}^{-1}(x) \approx x\log x$. This heuristic implies that $S(m) \approx m \log m$, and so $T(n) \approx \exp \Theta(\log n \log \log n)$. Of course, at this point this is just an educated guess.
As a sanity check, suppose that $T(n) = \exp (\log n \log \log n)$, where all logarithms are base 2. Then \begin{align*} T(n) \log T(n) &= \exp (\log n \log \log n) \log n \log \log n \\ &= \exp (\log n \log \log n + \log \log n + \log \log \log n) \\ &= \exp (\log (2n) \log \log n + \log \log \log n). \end{align*} This is quite similar to $T(2n) = \exp (\log (2n) \log \log (2n))$ (though not the same).
• This is a good heuristic way of solving recurrences and $\exp(\log \cdot \log\log)$ is close. I was hoping for an exact solution but I will accept this answer if no exact solution is found. – Reinstate Monica Dec 25 '17 at 16:07