3
$\begingroup$

I am trying to find the worst case $Θ$ bound for the following recurrence equation: $$ T(n)=\sum_{i=1}^kT(a_i)+n+\lg k\sum_{i=1}^ka_i\quad where\quad n=1+\sum_{i=0}^ka_i\quad and\quad a_0\ge a_1, a_2, \dots,a_k\ge 1 $$ By master theorem, with $k=a_0=a_1=n/3$ and $a_2=a_3=\dots =a_k=1$, $T(n)=Θ(n\lg n)$. Now my freind and I guessed that the worst case of $T(n)$ is also $Θ(n\lg n)$, but we are not able to prove it.

My question is, what is the worst case bound of $T(n)$ and how to prove it?

Edit: By worst case I mean that $T(n)$ to be the maximum of the expression I wrote over all $k\ge1$ and $a_0\ge a_1,a_2,\dots,a_k\ge1$ such that $n=1+a_0+\dots+a_k$.

$\endgroup$
0

2 Answers 2

1
$\begingroup$

For starters, let's rewrite the recurrence as $$ T(n) \leq \max \sum_{i>0} T(a_i) + O(n\log n). $$ Suppose now that we could show that $T(m+1) - T(m)$ is increasing in $m$. In this case, it follows that we can assume that $a_2 = \cdots = a_k = 1$, and so $$ T(n) \leq \max T(a_1) + O(n\log n). $$ The largest that $a_1$ can get is $n/2$ (well, $(n-1)/2$), and so $$ T(n) \leq T(n/2) + O(n\log n). $$ Expanding this, we get $T(n) = O(n\log n)$.

Showing that $T(m+1) - T(m)$ (if this is indeed true) looks a bit messy, but potentially could be done in the spirit of the following lemma.

Lemma For all $a,b \geq 1$, we have $T(a+b) > T(a) + T(b)$.

Proof. Choose the $a_i,b_j$ for which $$ \begin{align*} T(a) &= \sum_{i=1}^k T(a_i) + a + \log k \sum_{i=1}^k a_i, \\ T(b) &= \sum_{j=1}^\ell T(b_j) + b + \log l \sum_{j=1}^\ell b_j. \end{align*} $$ Consider the sequence $c_0 = a_0+b_0$, $c_1,\ldots,c_t = a_1,\ldots,a_k,b_1,\ldots,b_\ell,1$, where $t = k+\ell+1$. This sequence sums to $a+b-1$ and satisfies $c_0 \geq c_r \geq 1$ for all $r > 0$, and so $$ \begin{align*} T(a+b) &\geq \sum_{i=1}^k T(a_i) + \sum_{j=1}^\ell T(b_j) + T(1) + a+b + \log(k+\ell+1) \left(\sum_{i=1}^k a_i + \sum_{j=1}^\ell b_j + 1\right) \\ &> T(a) + T(b). \end{align*} $$

$\endgroup$
4
  • $\begingroup$ You claimed that $\max \sum_{i>0} T(a_i) + n + \log k \sum_{i>0} a_i \le T(n/2) + O(n\log n)$, but I don't think $\sum_{i>0}a_i\le n/2$. Can you explain more? $\endgroup$ Commented Mar 22, 2014 at 3:24
  • $\begingroup$ You're right, the argument doesn't work... but I believe that an argument along the same lines should. $\endgroup$ Commented Mar 22, 2014 at 3:30
  • $\begingroup$ Here is what I had in mind. It is conjectural at this stage – you could try proving the missing lemma. It is enough for $T(m+1) - T(m)$ to be increasing for large enough $m$ (in case it fails for stupid reasons for small $m$). $\endgroup$ Commented Mar 22, 2014 at 3:43
  • $\begingroup$ Assume that $cn\log n\le T(n)\le dn\log n$ for some constant $c, d$ and $2d<3c$, then let $k=3c$, $ a_1=\dots=a_{2d}=n/3c, a_{2d+1}=\dots=a_k=1$, then $T(n)\ge2dT(n/3c)+O(n\log n)\ge$ $(2/3)dn\log n+O(n\log n)\gt(1/2)dn\log n+O(n\log n)\ge T(n/2)+O(n\log n)$, which leads to contradiction in your proof (though I can't explain the assumption $2d<3c$). I don't think we can assume that $a_2=\dots=a_k=1$ so fast. $\endgroup$ Commented Mar 22, 2014 at 5:46
0
$\begingroup$

From the division-into-2 case, I'd guess that the worst case is the most unequal division possible, i.e., $a_0 = n - k$ and $a_1 = \ldots = a_k = 1$. Let's check: $$ T(n) = T(n - k) + k T(1) + n + k \lg k $$ This gives $T(n) = O(n^2)$.

$\endgroup$
1
  • 1
    $\begingroup$ It's $T(n)=\sum_{i=1}^kT(a_i)+...$, not $T(n)=\sum_{i=0}^kT(a_i)+...$. $\endgroup$ Commented Mar 22, 2014 at 0:39

Your Answer

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

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