# Solving recurrence

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?

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

• The upper bound can also be found in Sung-Hyuk Cha's paper, using a slightly different method. Commented Apr 25, 2020 at 18:15