I am currently solving a problem that I have reduced to computing the following function efficiently.

$$T_k(n) = T_k\left(\left \lfloor \frac{n}{2} \right \rfloor\right) + T_k\left(\left \lceil \frac{n}{2} \right \rceil\right)$$

The base cases are $\forall n < k: T_k(n) = 0$ and $\forall k \leq n < 2k: T_k(n) = 1$ Note: $n$ and $k$ are non-negative integers.

I need to compute this function for multiple values of $k$ and $n$.
I can compute this function in $\theta(n)$ by a simple recursive function using just the definition and speed up the computation by using memoization. However, this isn't fast enough and I was wondering if there is a closed form expression for it and can be computed in $o(n)$.

I have no idea how to solve this recurrence.

  • $\begingroup$ The special case $k=2$ has an explicit formula, see the OEIS entry and the links therein. $\endgroup$ Dec 25 '16 at 18:29

Observe that $T_k(2^n k) = 2^n$. Furthermore, it is easy to see that either $T_k(\alpha) = T_k(\alpha-1)$ or $T_k(\alpha) = 1+T_k(\alpha-1)$. Using the previous two results, it can also be shown that $T_k(2^n k - 2^{n-1}) = T_k(2^{n-1} k)$.

Now, consider $$\delta_k(n) = T_k(2^n k - 2^{n-1} + 1) - T_k(2^n k - 2^{n-1} )$$

It should be easy to prove by induction that for all $k, n$ it holds that $\delta_k(n) = 1$. This should be sufficient to uniquely determine the value of $T_k(n)$ for all $n$.

  • $\begingroup$ Can you please expand on how that would be sufficient to determine $T_k(n)$, maybe with a small example? I don't understand. $\endgroup$ Dec 25 '16 at 19:04
  • 1
    $\begingroup$ It follows from all the lemmata. Example, let k=3. We have that T(24 = 3 * 2^3) = 8. Also, T(20 = 3 * 2^3 - 2^2) = T(12 = 3 * 2^3) = 4 and T(21) = 5. Because T(x) - T(x-1) ≤ 1, the values of T(22), T(23) are necessarily 6 and 7. It's easy (but lengthy and boring) to write a closed formula by cases, and similarly easy (but every bit as lengthy and boring) to prove its correctness by Cauchy induction. $\endgroup$
    – quicksort
    Dec 25 '16 at 19:18

While working through the equalities that quicksort mentioned, I noticed the generalization $T_k(2^n j) = 2^n \text{ for } j \in \{ k \text{..} 2 k-1\}$

Then I calculated some values for k=3:

$2^n j$ = {3..5; 6..10; 12..20; 24..40; 48..80; 96..160}

$T_3(...)$ = {1; 2; 4; 8; 16; 32}.

and I noticed that the groups are separated by just enough numbers for the value to increase by at most 1. This leads to the following algorithm (in python3):

def Tk(k, n):
    if n < k:
        return 0
    if n < 2 * k:
        return 1
    a = math.floor(math.log(n/k, 2))
    end = pow(2, a) * (2*k-1)
    if n > end:
        return pow(2, a) + (n - end)
    return pow(2, a)

The definition leads directly to the (rather) closed formula

$T_k(n) = 0$ for $0 ≤ n < k$

$T_k(n) = 1$ for $k ≤ n < 2k$

$T_k(n) = 2^m$ for $2^mk ≤ n ≤ 2·2^mk-2^m$

$T_k(n) = 2·2^m - j$ for $n = 2·2^mk-j$, $2^m > j ≥ 1$

Proof: Assume n is the smallest counter example and check it gives the result as proposed.


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.