Case 11: According to the above cases, the literal x that isn't a singleton may occur in a 5-clause. So at least ten variables can be removed due to x=*true*. When *x=false*, at least the variable x can be removed. The time needed is bounded by T(n)=T(n-10)+T(n-1) with solution O(1.1975n).

Case 12: Each of the remaining clauses is 5-clause with one singleton based on the previous cases. The similar case as 7 when (x*y)=true* and this makes five variables remove. When *z=true*, at least nine variables are removed. In addition, five variables are removed because the similar case as 8 occurs when (p*q)=true*. So the time needed in this case is bounded by T(n)=T(n-9)+T(n-5)+T(n-5) with solution O(1.1995n).

In total, \#XSAT3 runs in O(1.1995n) time. □

![0_image_0.png](0_image_0.png)

Theorem 4. Algorithm \#XSAT runs in O(1.1995n) time, where n is the number of the variables.

Proof. Let us analyze the algorithm case by case.

Case 1and 2: These cases run in O(1).

Case 3: This case doesn't increase the time needed.

Case 4: It is easy to see that the worst case occurs when the all variable x occurs in the 3-clauses because in a reduced formula the length of the clause is at least three by Theorem 2. So when *x=true*, seven variables are removed; when x=*false*, 
five variables are removed. The time needed is bounded by T(n)=T(n-7)+T(n-5) with solution O(1.1238n).