1
$\begingroup$

I have a function whose time complexity is given by the following recurrence:

\begin{equation*} T(n) = \begin{cases} \mathcal{O}(1) & \text{for } n=0\\ T(k)+T(k-1)+\mathcal{O}(1) & \text{for } n=2k\\ T(k)+\mathcal{O}(1) & \text{for } n=2k+1\\ \end{cases} \end{equation*}

and I have to prove that $$T(n)\in \mathcal{O}(\phi^{\log_2 n}),$$

where $\phi$ is the golden ratio, $(1 + \sqrt5)\over2$.

I think I could prove it by induction but, how would I go on about it if I didn't know that $T(n)\in \mathcal{O}(\phi^{\log_2 n})$ in the first place?

$\endgroup$
  • $\begingroup$ is $\phi$ here the golden ratio (which is constant)? $\endgroup$ – nir shahar May 29 at 22:19
1
$\begingroup$

Your sequence (shifted by 1) is known as Stern's diatomic sequence, or the Stern–Brocot sequences. The usual recurrence is: \begin{align} &a(0)=0 \\ &a(1)=1 \\ &a(2n) = a(n) \\ &a(2n+1) = a(n) + a(n+1) \end{align} The recurrence suggests that the answer has something to do with binary representation, so one might be prompted to look at the maximal value of $a(n)$ among numbers of length $m$ in binary: $$ 1,2,3,5,8,13,\ldots $$ This is the Fibonacci sequence. (One can check that the first maxima are attained at $(2^n-(-1)^n)/3$.)

From here, one immediately sees that the rate of growth is $O(\phi^{\log_2 n})$.

More can be said. For example, Coons and Tyler determined the best possible constant in front of $\phi^{\log_2 n}$ in their paper The maximal order of Stern's diatomic sequence.

You can find many more links in the OEIS entry A002487.

| cite | improve this answer | |
$\endgroup$

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.