Solving recurrence

Question

How to solve the recursion:

$ T(n) = \begin{cases} T(n/2) + O(1), & \text{if $n$ is even} \\ T(\lceil n/2 \rceil) + T(\lfloor n/2 \rfloor) + O(1), & \text{if $n$ is odd} \end{cases} $

I think $T(n)$ is $O(\log n)$. Can somebody show a proof?

Answer 1

Your function appears in Sung-Hyuk Cha, On Parity based Divide and Conquer Recursive Functions.

Let us consider the following version: $$ T(n) = \begin{cases} 0 & \text{if } n = 0,1, \\ 2 & \text{if } n = 2, \\ T(n/2) + 1 & \text{if } n \geq 4 \text{ is even}, \\ T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + 1 & \text{if } n \geq 3 \text{ is odd}. \end{cases} $$ You can calculate that $$ T\left(\frac{7 \cdot 2^n - (-1)^n}{3}\right) = 2F_{n+4} - 2F_{n+1} - 2. $$ For example, $T(2) = 2$, $T(5) = 6$, $T(9) = 10$ (these correspond to $n=0,1,2$).

This gives an infinite sequence of $n$'s such that $$ T(n) = \Theta(n^{\log_2 \phi}), $$ where $\phi$ is the golden ratio. Empirically, this sequence maximizes the exponent.

The limiting exponent is roughly $0.694241913630617$.

See the related sequences A215673 and A215675, which correspond to slightly different initial conditions.

The sequence of worst-case inputs is A062092, and that of worst-case outputs is A001595.

---

Let us prove the claimed formula. Let $a_n = [7 \cdot 2^n - (-1)^n]/3$. Then $a_0 = 2$, and $a_n = 2a_{n-1} - (-1)^n$ for $n > 0$. If $n > 0$ is even then $$ \begin{align*} T(a_n) &= 1 + T(a_{n-1}) + T(a_{n-1} - 1) \\ &= 1 + T(a_{n-1}) + T(2a_{n-2}) \\ &= 2 + T(a_{n-1}) + T(a_{n-2}). \end{align*} $$ Similarly, if $n>1$ is odd then $$ \begin{align*} T(a_n) &= 1 + T(a_{n-1}) + T(a_{n-1}+1) \\ &= 1 + T(a_{n-1}) + T(2a_{n-2}) \\ &= 2 + T(a_{n-1}) + T(a_{n-2}). \end{align*} $$ Denoting $b_n = T(a_n)/2$, we get $b_0 = 1$, $b_1 = 3$, and $b_n = b_{n-1} + b_{n-2} + 1$ for $n \geq 2$. The sequence $b'_n = b_n + 1$ satisfies the recurrence $b'_n = b'_{n-1} + b'_{n-2}$, from which it is easy to find an explicit formula.

---

In the other direction, let us notice that when $n$ is odd, exactly one of $\lfloor n/2 \rfloor,\lceil n/2 \rceil$ is odd, and the other is even. This shows that for all $n$, we have $$ T(n) \leq T(n/2 + O(1)) + T(n/4 + O(1)) + O(1). $$ According to the Akra–Bazzi theorem, the solution to this recurrence is $T(n) = O(n^p)$, where $p$ is the solution to $$ \frac{1}{2^p} + \frac{1}{4^p} = 1. $$ (To deduce that from the theorem requires a bit of work; briefly, you compare $T$ to another recurrence $T'$ which is defined like $T$ on odd inputs but in a different way for even inputs; $T'$ satisfies the recurrence above exactly, and induction shows that $T \leq T'$.)

Let $x = 2^p$. Then $1/x + 1/x^2 = 1$, and so $x^2 = x + 1$. This is the familiar Fibonacci recurrence, with solutions $x = (1 \pm \sqrt{5})/2$. Only one of them is positive, and we conclude that $p = \log_2 \phi$. Therefore $$ T(n) = O(n^{\log_2 \phi}). $$ As we have seen above, the exponent is tight for infinitely many $n$. Since these $n$ are dense enough, we can conclude that $$ \max (T(0),\ldots,T(n)) = \Theta(n^{\log_2 \phi}). $$