Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question

1 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)}.$$

share|improve this answer
    
I think you're missing a square in your last expression. –  Antonio Vargas Jul 24 '13 at 14:18
1  
@AntonioVargas: No. $\log T(n) = c(\log n)^2$ means $T(n) = \exp(c \log n \log n) = n^{c \log n}$. Alternatively, I could write $T(n) = c^{(\log n)^2}$, to keep the square, but the point of writing it as $n^{c \log n}$ is to be suggestive about the rate of growth of this function versus polynomial growth. –  ShreevatsaR Jul 24 '13 at 15:02
    
Oh you're completely right. I misread it as $e^{O(\log n)}$ instead of $n^{O(\log n)}$. –  Antonio Vargas Jul 24 '13 at 15:25
    
BTW, the choice of $T(1) = 1$ does not lose any generality: with $T(1) = k$, the values are $1k, 2k, 4k, 6k, 10k, 14k, 20k, 26k, 36k, 46k, \dots$, i.e., the same sequence scaled by $k$. This does not affect the asymptotic order of growth. –  ShreevatsaR Jul 25 '13 at 4:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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