# Show that recurrence is $O(\phi^{\log n}) 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? • is$\phi\$ here the golden ratio (which is constant)? – nir shahar May 29 at 22:19

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.