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

$\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
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.

1

$\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