Is this algorithm for Exact Three Cover sub-exponential, because I find $length(s)/3$ combinations for $C$?

Question

Given an input $S$ (set of elements) find an exact three cover for a list of 3-element sets named $C$.

$S$ = 1,2,3,4,5,6

$C$ = [1,2,3],[4,5,6],[3,1,2]

Algorithm

1.Sort list and delete occurrences of sets that repeat in $C$.

• (eg. $[1,2,3]$ repeats because of $[3,1,2]$. Of course leave one of the sets.)

2.Remove sets that have elements that do not exist in $S$.

• (eg $[1,2,9]$... $9$ does not exist in $S$)

3.Remove sets with repeating elements.

• (eg. $[1,2,2]$ is deleted from $C$)

4.Remove repeating sets

• (eg. $[1,2,3]$ and $[1,2,3]$ but leave $[1,2,3]$)
• After $C$ has been sorted; the worst-case length of $C$ will be $\frac{lenght(s)!}{\left(3!\left(length(s)-3\right)!\right)}$

5.Use $length(s)$/$3$ for $K$ combinations of $C$.

• (eg. there will be $2$ sets required for an Exact Three Cover of $S$ $[1,2,3]$,$[4,5,6]$)

It seems the number of combinations will be < $2$^$\frac{lenght(s)!}{\left(3!\left(length(s)-3\right)!\right)}$ at least most of the time.

Question

Is this algorithm sub-exponential at least on average?

Answer 1

No. Exponential time is sometimes used to mean running times in $2^{\Theta(n)}$, and other times it is used to mean running times in $2^{\Theta(n^k)}$ for some constant $k>0$.

Your algorithm is exponential w.r.t. the second definition and superexponential w.r.t. the first. In fact your algorithm takes time $2^{\Theta(n^3)}$, where $n = |S|$ (notice that $\frac{n!}{3! \cdot (n-3)!} = \frac{n(n-1)(n-2)}{6} =\Theta(n^3)$).