Is below sorting algorithm O(n)?

Question

Algorithm:

insert element counts in a map
start from first element
if first is present in a map, insert in output array (total number of count), increment first
if first is not in a map, find next number which is present in a map

Complexity: O(max element in array) which is linear, so, O(n).

vector<int> sort(vector<int>& can) {
    unordered_map<int,int> mp;
    int first = INT_MAX;
    int last = INT_MIN;
    for(auto &n : can) {
        first = min(first, n);
        last = max(last, n);
        mp[n]++;
    }
    vector<int> out;
    while(first <= last) {
        while(mp.find(first) == mp.end()) first ++;
        int cnt = mp[first];
        while(cnt--) out.push_back(first);
        first++;
    }
    return out;
}

@SomeDude It's O(n + k) where k = (last - first), not O(n) - the Wikipedia page you linked to says this, too. — kaya3
– kaya3, Commented Feb 22, 2020 at 2:57

kaya3 · Accepted Answer · 2020-02-22 03:12:29Z

Complexity: O(max element in array) which is linear, so, O(n).

No, it's not O(n). The while loop iterates last - first + 1 times, and this quantity depends on the array's contents, not the array's length.

Usually we use n to mean the length of the array that the algorithm works on. To describe the range (i.e. the difference between the largest and smallest values in the array), we could introduce a different variable r, and then the time complexity is O(n + r), because the first loop populating the map iterates O(n) times, the second loop populating the vector iterates O(r) times, and its inner loop which counts down from cnt iterates O(n) times in total.

Another more formal way to define n is the "size of the input", typically measured in the number of bits that it takes to encode the algorithm's input. Suppose the input is an array of length 2, containing just the numbers 0 and M for some number M. In this case, if the number of bits used to encode the input is n, then the number M can be on the order of O(2ⁿ), and the second loop does that many iterations; so by this formal definition the time complexity is exponential.

Collectives™ on Stack Overflow

Is below sorting algorithm O(n)?

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related