Time complexity of this implementation of counting sort

Question

I have to determine the time complexity for the given code of counting sort. I know that counting sort should be O(n+k) but I just can't see how this function is O(n+k), seeing as there is a for loop inside the second for loop.

def counting_sort(array, k): # k is max(array)

    count = (k+1) * [0]  
    sorted = []
    for i in array:
        count[i] += 1
    for i in range(len(count)):
        if count[i] != 0:
            sorted += [i for j in range(count[i])]
    return sorted

Wouldn't the worst case be n+k^2, if the elements are unique?

The inner loop (comprehension) increases your complexity from k to n because it expands the non-singular elements — Mad Physicist
– Mad Physicist, Commented Apr 25, 2019 at 17:59
No, because the inner loop only loops count[i] times, not k times. — Blorgbeard
– Blorgbeard, Commented Apr 25, 2019 at 17:59
If there's only a single repeating element, the inner loop would only execute once. In the end, your loops are always performing "add an element to the array" exactly n times. — Blorgbeard
– Blorgbeard, Commented Apr 25, 2019 at 18:02

Juan Carlos Ramirez · Accepted Answer · 2019-04-25 18:32:18Z

2

The first loop

for i in array:
    count[i] += 1

takes n iterations, for the second loop the number of instructions executed in the worst case scenario for the list comprehension:

i for j in range(count[i]) #

is count[i], and the sum of all count[i] is equal to n. Note that the comparison

        if count[i] != 0:

is done k times, and in the worst case scenario the

sorted +=...

is also done k-times. Adding all this up you get your O(n+k)

(assuming the += for sorted is constant cost, otherwise we have to say that the += is amortized constant and so the result comes with that caveat).

edited Apr 25, 2019 at 18:32

answered Apr 25, 2019 at 18:21

Juan Carlos Ramirez

2,1551 gold badge10 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

f17f Over a year ago

So the list comprehension will run max n times, with the comparison running k times, wouldnt that make it n*k?

Juan Carlos Ramirez Over a year ago

No, because the list comprehension cannot run n times for every k. the total sum of list comprehension iterations is equal to the sum of count[i] which is exactly n.

Juan Carlos Ramirez Over a year ago

For example if you have an iteration where the list comprehension is of size n, then for all other iterations, the list comprehension is of size 0 (this only happens when all entries in the array have the same value).

f17f Over a year ago

Gotcha, but if the list comprehension runs n times it would have O(n) and taking into account the first for loop it would give O(n+n)?

Juan Carlos Ramirez Over a year ago

In part, but you would still have k comparisons even if you are not in the worst case scenario.

Collectives™ on Stack Overflow

Time complexity of this implementation of counting sort

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related