haskell / haskell/containers

Improve powerSet performance

Open
#890 53 comments 0 reactions 0 assignees View on GitHub
performance Set
Dominant language
Haskell
Stars
355
Forks
194
Avg merge
3d 4h
Merged PRs (30d)
4

Description

Obviously, there's only so much we can do, but we can do some. The most obvious optimization is to use a version of `insertMin` that takes a singleton tree as an argument instead of an element. But I can't help wondering if we can do better. The problem is obviously $\Omega(2^n)$, and our solution is $O(2^n\log n)$. Can we close that gap by either improving our solution or proving a tight(er) lower bound?

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.