Analyzing the number of phases required

The number of phases used in the Complete solution is characterized by the following theorem.

Theorem 6   The Complete solution uses at most $OPT(G)+1$ phases to well-represent any distribution $G\in {\cal PH}_3$.

Proof:If $G\in\cal{PH}_3^-$, the number of phases used in the Complete solution is at most that used in the Simple solution, i.e. $\leq \mbox{OPT}(G) + 1$. Thus, it suffices to prove that if a distribution $G\in ({\cal T}^{(n)}\setminus {\cal T^{(n-1)}})\cap(\cal{PH}_3^-)^c$, then at most $n+1$ phases are needed (recall ${\cal S}^{(n)}\subset {\cal T}^{(n)}$ by Lemma 1). If $G\in ({\cal T}^{(n)}\setminus {\cal T}^{(n-1)})\cap (\cal{PH}_3^-)^c \cap \widehat{{\cal U}}$, then $m_2^G = n / (n-1)$. Thus, by (2.7), the number of phases used is $n+1$. If $G\in ({\cal T}^{(n)}\setminus {\cal T}^{(n-1)})\cap (\cal{PH}_3^-)^c \cap (\widehat{\cal M} \cup \widehat{\cal L})$, then the number of phases given by (2.8) is exactly $n$, except for input distribution $G$ with $m_2^G\geq 2$ and $r^G=3/2$ (i.e. exponential distribution possibly mixed with $O$) for which (2.8) gives 1. Thus, the number of phases used in the Complete solution for $G\in (\cal{PH}_3^-)^c \cap (\widehat{\cal M} \cup \widehat{\cal L})$ is $\mbox{OPT}(G)$.     width 1ex height 1ex depth 0pt

Theorem 6 implies that any distribution in ${\cal S}^{(n)}$ is well-represented by an EC distribution of $n+1$ phases. In the proof, we prove a stronger property that any distribution in ${\cal T}^{(n)}$, which is a superset of ${\cal S}^{(n)}$, is well-represented by an EC distribution of $n+1$ phases, which implies the following corollary:

Corollary 3   For all integers $n \geq 2$, ${\cal T}^{(n)} \subset {\cal S}^{(n+1)}$.