4
$\begingroup$

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?

Edit: cross-posted here.

$\endgroup$
5
  • $\begingroup$ Then why wouldn't you plug something barely super-polynomial, like $\exp(\log n\cdot\log\log n)$? $\endgroup$
    – Ivan Neretin
    Dec 25, 2017 at 9:17
  • $\begingroup$ @IvanNeretin I have tried that function, and in the cross post, you can see that someone answered the question with that function. However, it isn't quite right. $\endgroup$
    – Reinstate Monica
    Dec 25, 2017 at 16:20
  • $\begingroup$ Yes, I know, but at least this is a step in the right direction. $\endgroup$
    – Ivan Neretin
    Dec 25, 2017 at 16:22
  • $\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$ I'm closing this question because further answers should better be posted on Computer Science now that it has a first answer there. $\endgroup$
    – Daniel Fischer
    Dec 26, 2017 at 19:09

0

Reset to default