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?

  • $\begingroup$ 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. $\endgroup$
    – JimN
    Dec 25, 2017 at 6:32
  • 1
    $\begingroup$ T(n) = 2 is a solution :) $\endgroup$
    – gnasher729
    Dec 25, 2017 at 11:31
  • $\begingroup$ “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. $\endgroup$
    – gnasher729
    Dec 25, 2017 at 11:39
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Dec 26, 2017 at 17:32
  • $\begingroup$ @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? $\endgroup$ Dec 26, 2017 at 18:29

2 Answers 2


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

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

Your Answer

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

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