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, 2017 at 6:32
• T(n) = 2 is a solution :) Dec 25, 2017 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. Dec 25, 2017 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, 2017 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? Dec 26, 2017 at 18:29

We shall asymptotically solve $$\color{blue}{ f(2n) = f(n)·\log(f(n))·2^c }$$ for any $$c∈ℝ$$ as $$n → ∞$$ (where $$\log = \log_2$$). $$\def\lfrac#1#2{{\large\frac{#1}{#2}}}$$

~ ~ ~

Note that $$\log\log(2n) = \log(\log(n)+1)$$ $$= \log\log(n)+\lfrac{r}{\log(n)}+\cdots$$ where $$r = \lfrac1{\ln(2)}$$. (Omitted terms are asymptotically smaller.)

And $$\log\log\log(2n) = \log\big(\log\log(n)+\lfrac{r}{\log(n)}+\cdots\big)$$ $$= \log\log\log(n)+\lfrac{r^2}{\log(n)·\log\log(n)}+\cdots$$.

Let $$g$$ be a function such that $$f(n) = 2^{\log(n)·\log\log(n)+g(n)}$$. We shall take for granted (I believe it can be proven with some effort) that $$g(n) ≪ \log(n)·\log\log(n)$$.

Then $$f(2n) = 2^{\log(2n)·\log\log(2n)+g(2n)}$$

$$= 2^{\log(2n)·\big(\log\log(n)+\lfrac{r}{\log(n)}+\cdots\big)+g(2n)}$$

$$= 2^{\log(2n)·\log\log(n)+g(2n)+r·\big(1+\lfrac1{\log(n)}\big)+\cdots}$$.

And $$f(n)·\log(f(n))·2^c$$

$$= 2^{\log(n)·\log\log(n)+g(n)+\log(\log(n)·\log\log(n)+g(n))+c}$$

$$= 2^{\log(n)·\log\log(n)+g(n)+\log(\log(n)·\log\log(n))+\lfrac{r·g(n)}{\log(n)·\log\log(n)}+c}$$

$$= 2^{\log(2n)·\log\log(n)+g(n)+\log\log\log(n)+c+\lfrac{r·g(n)}{\log(n)·\log\log(n)}}$$.

Thus $$g(2n)-g(n) = \log\log\log(n)+(c-r)−\lfrac{r}{\log(n)}+\lfrac{r·g(n)}{\log(n)·\log\log(n)}+\cdots$$.

So $$g(2^{k+1})-g(2^k) = \log\log(k)+(c-r)+\cdots$$ as $$k → ∞$$.

Thus $$g(2^k) = \sum_{i=2}^{k-1} \log\log(i) + k·(c-r) + \cdots$$.

$$= k·\log\log(k) + k·(c-r) + \cdots$$.

Thus $$g(n) = \log(n)·\log\log\log(n)+\log(n)·(c-r)+\cdots$$.

Therefore $$\color{blue}{ f(n) = 2^{\log(n)·(\log\log(n)+\log\log\log(n)+(c-r)+\cdots)} }$$.

~ ~ ~

To check, letting $$f_1(n) = 2^{\log(n)·(\log\log(n)+\log\log\log(n)+(c-r))}$$ we get:

$$\log(f_1(2n))$$

$$= \log(2n)·(\log\log(2n)+\log\log\log(2n)+(c-r))$$

$$= (\log(n)+1)·\big(\log\log(n)+\log\log\log(n)+(c-r)+\frac{r}{\log(n)}+\cdots\big)$$

$$\log(f_1(n)·\log(f_1(n))·2^c)$$

$$= \log(n)·(\log\log(n)+\log\log\log(n)+(c-r))+\log\log(n)+\log\log\log(n)+c+\cdots$$.

So $$\log(f_1(2n)) - \log(f_1(n)·\log(f_1(n))·2^c) = \frac{r}{\log(n)} + \cdots$$, as expected.

~ ~ ~

It may be possible to get an exact asymptotic solution, since we just have to find some $$h$$ such that $$f(n) ∈ 2^{\log(n)·\big(\log\log(n)+\log\log\log(n)+(c-r)+h(n)+O(\lfrac1{\log(n)})\big)}$$, but I'm not sure it's worth the trouble.

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. Dec 25, 2017 at 16:07
• See my answer for a much more precise asymptotic analysis. =) Jun 7, 2022 at 0:26