CODEWITHSUNDEEP
sortingcounting
DTT
DTT

Reputation: 3

Counting sort running time

The code fragment below from this link 

int[] countingSort(int[] a, int k) {
        int c[] = new int[k];
        for (int i = 0; i < a.length; i++)    //{1}
            c[a[i]]++;
        for (int i = 1; i < k; i++)           //{2}
            c[i] += c[i-1];
        int b[] = new int[a.length];
        for (int i = a.length-1; i >= 0; i--) //{3}
            b[--c[a[i]]] = a[i];
        return b;
}

It states that the running time is O(n+k) time .k is the range of input array a .

Can anyone explain why the running time is O(n+k). ?

If we look at the code fragment and see that the {1} for loop runs in n time , {2} runs in K time and the third runs in also n time So total run time should be O(2n+k) time . Is my calculation incorrect? Is the constant 2 ignored here ?

Upvotes: 0

Views: 89

Answers (1)

erkanyildiz
erkanyildiz

Reputation: 13214

Your calculation is also correct, because O(2n+k) = O(n+k).

For time complexity, only the polynomial degree is important, not the coefficients.

So; O(n) = O(2n) = O(3n) .... = O(xn)

Please read https://en.wikipedia.org/wiki/Time_complexity#Linear_time

Upvotes: 1

Related Questions