1
$\begingroup$

I have been working in the time analysis for an exact solver I designed for the subset sum problem accepting multisets as input instances, and determined its time complexity to be dependent on the multiplicity ($m$) of the elements in the input.

For input instances containing elements having $m \leq 2$, the time complexity is $O(2^{n/2} \cdot 0.75^{\frac{d/2}{n}})$ where $d=$ # of elements with $m=2$.

For example, when $d=n/2$, then:

  • $O(2^{n/2} \cdot 0.75^{\frac{d/2}{n}}) \approx O((1.4142 \cdot 0.93)^n) \approx O(1.316^n)$

For input instances containing elements having $m = 1 $ and $m=4$, the time complexity is $O(2^{n/2} \cdot 0.312^{\frac{d/2}{n}})$ where $d=$ # of elements with $m=4$.

For example, when $d=n/4$, then:

  • $O(2^{n/2} \cdot 0.312^{\frac{d/2}{n}}) \approx O((1.4142 \cdot 0.86)^n) \approx O(1.223^n)$

And following the above configuration, for $m=8$ and $d=n/8$ is

  • $O(2^{n/2} \cdot 0.035^{\frac{d/2}{n}}) \approx O((1.4142 \cdot 0.81)^n) \approx O(1.147^n)$

I have yet to complete the time analysis for mixed cases (different multiplicities in the input instance) but my educated guess is it will be a composite of the above TCs.

Besides to ask for comments, I am looking as well for other known algorithms with a similar behavior to compare approaches (looked for them but found nothing so far...)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.