counting sort complexity

[andrix]

hi there

is this counting-sort function O(n) even though the nested for-while?
where n is the dimension of v.

void counting_sort(vector<int>& v)
{
int max,min;
max=max_vett(v);
min=min_vett(v);

vector<int> c(max-min+1,0);

for(int i=0;i<v.size();i++)
c[v[i]-min]++;
int k=0;
for(int j=0;j<c.size();j++)
{
while(c[j]>0){
v[k]=j+min;
k++;
c[j]--;
}

}

[abhishekm71]

I haven't gone through the algorithm logic, but the complexity does seem to be ~O(n).

If you sum up all the elements in the c vector, you will get the number of elements (N) in the v vector. So the following loop basically performs N iterations:

for(int j=0;j<c.size();j++)
{
   while(c[j]>0){

      //do something;
      c[j]--;
    }
}

[Josue Molina]

For the worst case, set every

v[j] = std::pow(2, sizeof(int) * 8 - 1) - 1;

This is a constant, call it c. Now, if n = v.size(), then this is an O(c * n) = O(n) algorithm.