2
$\begingroup$

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?

$\endgroup$
  • $\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 '17 at 6:32
  • 1
    $\begingroup$ T(n) = 2 is a solution :) $\endgroup$ – gnasher729 Dec 25 '17 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 '17 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 '17 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$ – Solomonoff's Secret Dec 26 '17 at 18:29
3
$\begingroup$

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

$\endgroup$
  • $\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$ – Solomonoff's Secret Dec 25 '17 at 16:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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