1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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