2
$\begingroup$

Given positive constants: $c_1, c_2, ..., c_k, c^\prime$, assume that
$T(n) = T(c_1n) + T(c_2n) + ...+ T(c_kn) + c^\prime n$

There are two cases:

  1. $c_1 + c_2 + ...+ c_k < 1$
  2. $c_1 + c_2 + ...+ c_k = 1$

As I observed (from some problems), in case 1 $T(n) = \theta{(n)}$, in case 2 $T(n) = \theta{(n\log{n})}$ But I didn't find the theory says this always true, so I'm wondering, generally is this true or a theorem or is there any counterexample?


For example, of Case 1 : $T(n) = T(\frac{n}{2}) + T(\frac{n}{4}) + T(\frac{n}{8}) + n = \theta{(n)}$
and of Case 2 : $T(n) = T(\frac{n}{3}) + T(\frac{2n}{3}) + n = \theta{(n\log{n})}$

$\endgroup$
  • 3
    $\begingroup$ Look up the Akra-Bazzi theorem. $\endgroup$ – Yuval Filmus Dec 25 '18 at 5:59
3
$\begingroup$

Your observation is correct. More specifically, we have the following proposition.

(Asymptotic behavior of a kind of linear recurrence) Suppose $T(n)\ge0$ is defined for all $n$ greater than some constant. $$T(n) = T(c_1n+h_1(x)) + T(c_2n+h_2(n)) + ...+ T(c_kn+h_k(n)) + c n$$ where $c_1, c_2, ..., c_k, c$ are positive constants smaller than 1 and $h_1, h_2, ..., h_k$ are functions bounded by a constant. There are three cases.

  • If $c_1 + c_2 + ...+ c_k < 1$, then $T(n) = \Theta({n})$.
  • If $c_1 + c_2 + ...+ c_k = 1$, then $T(n) = \Theta(n\log n)$.
  • If $c_1 + c_2 + ...+ c_k > 1$, then $T(n) = \Theta(n^p)$, where $p$ satisfies $\sum_{1 \le i \le k} {c_i}^{p} = 1$.

Note that $h_i(n)$ represents a small perturbation in the index of $T$. Since $\lfloor c_{i}x\rfloor =c_{i}x+(\lfloor c_{i}x\rfloor -c_{i}x)$ and that the absolute value of $\lfloor c_{i}x\rfloor -c_{i}x$ is always between 0 and 1, $h_{i}(n)$ can be used to ignore the floor function in the index. Similarly, one can also ignore the ceiling function. For example, $T(n) = T(\lfloor\frac{n}{2}\rfloor) + T(\lfloor\frac{n}{4}\rfloor) + T(\lceil\frac{n}{8}\rceil) + n$ and $T(n) = T(\frac{n}{2}) + T(\frac{n}{4}) + T(\frac{n}{8}) + n$ will have the same asymptotic behavior. Because of this same asymptotic behavior, recurrence relations might be written sloppily from time to time when only their asymptotic behavior are the only concern, such as possibly the case of the current question.

The above proposition is just a special case of the more general situation handled by the Akra-Bazzi method, also explained here.

The question has provided examples for the first two cases of the proposition.

Here is an example of the third case. Let $$T(n)= T(\lfloor\frac12n\rfloor) + T(\lfloor\frac23n\rfloor) + T(\lfloor\frac56n\rfloor)+2019n$$ and $T(1)=0$. Since $(\frac12)^3+(\frac23)^3+(\frac56)^3=1$, we conclude that $T(n)=\Theta(n^3)$.


Exercise. How about $T(1)=1$ and $T(n)= T(\lceil\frac27n\rceil) + T(\lceil\frac37n\rceil) + T(\lceil\frac67n\rceil)+2018n$?

$\endgroup$

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.