CODEWITHSUNDEEP
c++
code_Up
code_Up

Reputation: 13

Complexity O(N) array and double for

How can i get complexity O(N)? i, currently, have a complexity O(N^2), right?

    vector<int> coins;
    vector<int> div;

    int n;
    cin >> n;

    int b, m;

    for (int k = 0; k < n; k++)
    {
        cin >> m;
        for (int i = 0; i < m; i++)
        {
            cin >> b;
            coins.push_back(b);
        }
    }

EDIT: code is here https://pastebin.com/bPG7D3W6

Upvotes: 0

Views: 127

Answers (2)

Mykhailo Bykhovtsev
Mykhailo Bykhovtsev

Reputation: 512

That is not O(N^2) by the way. That is O(N * M). Since you have two loops. One is from 0 to N and another nested loop from 0 to M. Maybe if you try to tell what you are trying to achieve, it would be easier to reformat the loops?

Currently I cannot see how to rework this loop with different complexity while maintaining functionality it has.

Edit:

@bitmask Made a great point in their answer. If you pre-allocate your vector, it will stop push_back() from re-allocating vector a lot. Re-allocation is O(N). The issue is that we do not have M constant, it varies on input of user. But you can perform cute optimization by allocating vector at least initially after you get n, to be size of n. The reason it is a cute optimization is because it will save you a bit of performance, but it won't be as significant that will impact your Big O. 

vector<int> coins;
vector<int> div;

int n;
cin >> n;

int b, m;


coins.reserve(n);
...

Upvotes: 5

bitmask
bitmask

Reputation: 34618

This algorithm has a complexity of O(n + m0 + ... + mn-1). In case all the mi are identical, this will result in O(n*m).

However, take a look at the complexity of the algorithm not in terms of its input but its output: You want to end up with a collection of c = coins.size(). As such it is impossible to have an agorithm that has complexity better than O(c).

Your algorithm runs in O(c) but seeing this is not trivial and depends on the specification of std::vector. A vector has amortised O(1) push_back, but non-amortised any given push_back can have complexity O(s) with s = vector.size() as it has to (potentially) allocate a new storage location of size 2*s and copy/move s objects. Still the amortisation means that you can hide all the copy/move overhead of std::vector inside the Big-O-notation as it is bound by C*c which is in O(c) for a constant C.

So, while you cannot improve the complexity of your algorithm, you can likely improve the effective performance of it. Namely by pre-allocating more buffer once you know any of the mi:

    cin >> m;
    coins.reserve(coins.size() + m);

This will reduce the number of allocations (by far the most expensive part of your program). To see the difference you cannot use Big-O analysis but have to measure the performance your program.

In case that your mi are likely to not vary greatly, you can even reserve n*m0 once you read your first m value. This will likely significantly reduce the runtime further.

If you want to completely optimise the performance, read all the mi in advance so that you can reduce the number of vector allocations to exactly 1. But this will change the order in which you read input.

Upvotes: 2

Related Questions