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

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?

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)$$).
• I asked because I was counting the amount of $length(s)/3$ combinations of being < 2**N for the length of C (as in worst case being all 3-combinations of S for C) Jun 13 '20 at 2:14