Is there any O(n^2) algorithm to generate all sub-sequences of an array?

Question

I was wondering if there is any O(n^2) complexity algorithm for generating all sub-sequences of an array. I know an algorithm but it takes O((2^n)*n) time.

int main() {
    int n; 
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i) 
        cin >> a[i];
    int64_t opsize = pow(2,n);
    for (int counter = 1; counter < opsize; counter++) {
        for (int j = 0; j < n; j++) {
           if (counter & (1 << j))
                 cout << a[j] << " ";
        }
        cout << endl;
    }
}

to improve performance you can replace `endl` with `'\n'`. – Marek R Jul 06 '18 at 15:34 — Marek R, Jul 06 '18 at 15:34

random40154443 · Accepted Answer · 2018-07-06T15:25:00.930

16

No

There cannot be any algorithm of less than O(2^n) complexity simply because there are O(2^n) sub-sequences. You need to print each of them hence the time complexity has to be greater than or equal to O(2^n).

edited Jul 06 '18 at 15:25

answered Jul 06 '18 at 15:14

random40154443

1,100
1
10
25

2

also, the longest sub-sequence will have a length of n, so as you need to iterate all the array, it will be (2^n)*n – Kepotx Jul 06 '18 at 15:15
You can directly infer that from the answer. I made it explicit. – random40154443 Jul 06 '18 at 15:24
Sorry, my `n` and `2` were backwards. Good answer – NathanOliver Jul 06 '18 at 15:27

Marek R · Answer 2 · 2018-07-09T17:30:32.743

1

You can't improve algorithm complexity, but you can improve how stream is used. As other answer points out o(n * 2^n) is best you can have.

When you use std::endl you are flushing buffers of streams. To achieve best performance buffers should flush them selves when they are full. Since each subsequence have to be quite short (at maximum 64 elements), it means that you are flushing stream quite often and have serious performance hit. So replacing std::endl with '\n' will provide significant performance improvement.

Other tricks which can help improve stream performance:

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n; 
    cin >> n;

edited Jul 09 '18 at 17:30

answered Jul 06 '18 at 15:51

Marek R

32,568
6
55
140

`IMO problem is not complexity, but way how stream is used`. The fact is that `endl` versus `\n` won't change anything. The algorithm will take **millions of years** to complete for even small values of `n` less than a hundred. – fjardon Jul 09 '18 at 06:49
You can't improve complexity as @DeepankarArya point out, so the only way you can improve performance is by improving code by removing bottle necks. This is what my answer does. Try it with data which can complete in reasonable time and see how big improvement it is. – Marek R Jul 09 '18 at 07:36
and implementation limits `n` to 62 items (still it will take ages). – Marek R Jul 09 '18 at 07:41
My point is that even if the only thing you can do is improve the I/O, the real problem **is** complexity, contrary to what you state in your answer. You don't answer the question `Is there any O(n^2) algorithm ?` – fjardon Jul 09 '18 at 12:03
I've point out that you can't improve algorithm complexity, I've rephrased first sentence to make it more clear. – Marek R Jul 09 '18 at 17:33

Is there any O(n^2) algorithm to generate all sub-sequences of an array?

2 Answers2

Linked