0
$\begingroup$

Could someone help me solve the following recurrence? $$ T(k) \le 1+\sum_{i=1}^{n_k}T(k_i), $$ where $n_k\le k$, $k_i\le \frac23 k$ $\forall i = 1, \dots n_k$, and $\sum_{i=1}^{n_k}k_i \le k$. The intuition behind the problem is that I have an algorithm that takes an instance of size $k$, splits it into $n_k\le k$ pieces each of size at most $\frac23 k$, and solves the problem recursively on each of the instances. I would like to know the runtime of the algorithm, but the only simplification of the recursion that I can think of is to say, ok, we can have at most $k$ pieces each with size at most $\frac 23k$, what gives the following simplification $$ T(k) \le 1+kT(\frac23k), $$ but this clearly cannot happen because we cannot have $O(k)$ pieces each of size $O(k)$, since then the size of the input instance must be $O(k^2)$.

$\endgroup$
  • $\begingroup$ Also we don't know exactly which piece has what size, we only know that each is at most $\frac 23$ of the input instance. $\endgroup$ – myro May 31 '18 at 12:49
3
$\begingroup$

You may prove a polynomial upper bound by induction. At first, denote $f(k)=T(k)+M$ for certain large $M$, this $f$ satisfies the inequality $f(k)\leqslant c\sum f(k_i) $ for some $c>0 $. Assume that we know the inequality $f(x) \leqslant Q x^a$ for the constants $Q>0, a>1$. Then the maximal value of $\sum k_i^a$ under your restrictions is $(2k/3)^a+(k/3)^a$ and if $c(2^a+1)/3^a<1 $, induction works.

$\endgroup$
  • 1
    $\begingroup$ Also, if $AC<1$ a linear bound holds. $\endgroup$ – Brendan McKay May 31 '18 at 13:10
  • $\begingroup$ Hi, thanks for the answer, actually I just realized that that the constants are not important form me. What matters is to give an upper bound on the worst partitioning of a number $k$ under the restrictions. $\endgroup$ – myro Jun 1 '18 at 11:50

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.