0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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)$).

$\endgroup$
1
  • $\begingroup$ 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) $\endgroup$ Jun 13 '20 at 2:14

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.