Strange Recurrence: What is it asymptotic to?

Question

So I have the following recurrence relation for the growth rate of an algorithm:

$T(n)$ = time taken by algorithm to solve problem of size n:

$$T(n) = T(n-1) + T(\lceil(n/2)\rceil)$$

Clearly this does not obey any polynomial law but now my question is what does it obey?

I merely want an asymptotic equivalence.

My guess is subexponential since this is faster than polynomial but clearly slower than any exponential form.

What though is the question....

Answer 1

With $T(1) = 1$, calculating the terms of the sequence gives successively $1, 2, 4, 6, 10, 14, 20, 26, 36, 46, \dots$, searching which on OEIS gives OEIS sequence A000123, which is the number of partitions of $2n$ into powers of $2$. Here, as we started with $T(1) =1$ instead of $T(0)=1$, we should say $T(n)$ is the number of partitions of $2n-2$ into powers of $2$.

We can be sure that it is the same sequence, following a proof given here: let $A(n)$ denote the number of partitions of $n$ into powers of $2$. Then:

• $A(2m+1) = A(2m)$, because any partition of $2m+1$ into powers of $2$ must necessarily contain "$1$" as one of the parts, and removing it gives a partition of $2m$ into powers of $2$.
• Similarly, $A(2m+2) = A(2m) + A(m+1)$, because any partition of $2m+2$ into powers of $2$ either contains a part "$1$" (which can be removed, so the number of such partitions is $A(2m+1) = A(2m)$) or else all the parts can be divided by $2$ to give a partition of $m+1$ into powers of $2$ (the number of such partitions is $A(m+1)$).

So, suppose we define $B(n) = A(2n-2)$. Then note that

• when $n$ is even, $B(\lceil n/2 \rceil) = A(2(n/2)-2) = A(n-2)$ (but $A(n-1) = A(n-2)$ as well)
• when $n$ is odd, $B(\lceil n/2 \rceil) = A((n+1) - 2) = A(n-1)$.

So $B(\lceil n/2 \rceil) = A(n-1)$ in either case. Therefore, $B(n)$ satisfies the same recurrence as $T(n)$: we have $B(n) = A(2n-2) = A(2n-4) + A(n-1) = B(n-1) + B(\lceil n/2 \rceil)$, and of course $B(1) = 1 = T(1)$, so $T(n) = B(n)$.

According to a comment by Philippe Flajolet there, the precise asymptotics of this sequence are given in a paper by N. G. de Bruijn called "On Mahler's Partition Problem" (1948, PDF), and is equivalent to:

$$ \log T(n) = \frac{1}{2\log 2}\left(\log \frac{n}{\log n}\right)^2 + \left(\frac12 +\frac1{\log \log 2} + \frac{\log \log 2}{\log 2}\right)\log n - O(\log \log n) $$ (a more precise expression down to the $O(1)$ term is given there).

This confirms the idea that $T(n)$ grows faster than polynomial and slower than exponential, as polynomials are those functions $f$ for which $\log f(n) \sim c\log n$ for some $c$, and exponentials are those for which $\log f(n) \sim cn$ for some $c$.

If you want a less precise bound to have a rough idea of its kind of growth, you can observe that $\log T(n) = O\left((\log n)^2\right)$ and therefore $$T(n) = n^{O(\log n)}.$$