2
$\begingroup$

I have a recurrence relation that looks like this:

$T(n) = 2 T(c n) + T((1-c)n) + O(1)$

The base case is just $T(b) = 1$ when $b \leq 1$.

I'm trying to figure out the best value of $c \in (0, 1)$ to use, to minimize the asymptotic growth rate.

For example, if I use $c=1/2$ then the recurrence simplifies to $3 T(n/2) + O(1)$ and it grows like $O(n^{lg_3 2}) \approx O(n^{1.585})$. (This is essentially the only case I've managed to solve, because it's the only one where the terms combine.)

I have found that changing the $c$ as I go can make solving easier. For example, alternating between $c_0, c_1 = \frac{1}{3}, \frac{1}{2}$ achieves $O(n^{lg_5 3}) \approx O(n^{1.465})$. In general if you cycle through $\frac{1}{p}, \frac{1}{p-1}, ..., \frac{1}{3}, \frac{1}{2}$ you get $O(n^{lg_p 2p-1}) \in O(n^{lg_p 2p}) = O(n^{1 + 1/lg_p 2}) \in O(n^{1 + \epsilon})$. This suggests that using a single $c$ will also allow getting arbitrarily close to linear, though we're hiding larger and larger constants so we can't just set $p=\Gamma^{-1}(n)$. And maybe the single best $c$ achieves $O(n \log(n))$, which would be better than $O(n^{1+\epsilon})$.

I've looked into how the branching plays out. I know that you end up summing terms like ${x \choose i} 2^i c^{x-i} (1-c)^x n$. But you need to iterate over the pairs of $x$ and $i$ that correspond to the final expansion before hitting 1 and even if I knew how to generate those analytically I doubt I'd be able to evaluate the resulting sum.

If it's the multiplying that's causing problems, transforming the problem into $T(p) = 2 T(p - lg(c)) + T(p - lg(1-c)) + 2^p$ might make things easier. I haven't found it helpful yet, though.

Any ideas?

$\endgroup$
1
$\begingroup$

Use Leighton's version of the master theorem: Consider a recurrence of the form: $$ T(z) = g(z) + \sum_{1 \le k \le n} a_k T(b_k z + h_k(z)) $$ fo $z \ge z_0$, $a_k$ and $b_k$ constants, with the restrictions:

  1. There are enough base cases
  2. For all $k$, $a_k > 0$ and $0 < b_k < 1$
  3. There is a constant $c$ such that $g(z) = O(z^c)$ when $z \to \infty$
  4. For all $k$ it is $\lvert h_k(z) \rvert = O(z / (\log z)^2)$

Then if $p$ is such that: $$ \sum_{1 \le k \le n} a_k b_k^p = 1 $$ the solution to the recurrence satisfies: $$ T(z) = \Theta\left( z^p \left( 1 + \int_1^z \frac{g(u)}{u^{p + 1}} \, \mathrm{d} u \right)\right) $$

Here the hypotheses are satisfied, you want $p$ such that:

$$ 2 c^p + (1 - c)^p = 1 $$

Smallest value is $p = 1$ for $c = 0$.

$\endgroup$
  • 1
    $\begingroup$ Your link is behind a paywall. Are these course notes talking about the same thing? $\endgroup$ – Craig Gidney Aug 24 '15 at 17:16
  • $\begingroup$ @Strilanc, didn't notice that. It seems to be the same result, edited the answer. Thanks" $\endgroup$ – vonbrand Aug 24 '15 at 18:00

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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