I have implemented RadixSort for a list of numbers (quite a similar implementation as e.g. this one, with the only difference that it uses a class RadixSort, which IMO shouldn't make any difference in terms of complexity):

class RadixSort:
    def __init__(self):
        self.base = 7
        self.buckets = [[[] for i in range(10)] for i in range(self.base)]  #list of sorting buckets, one bucket per digit

    def sort(self, list1d):
        """
        Sorts a given 1D-list using radixsort in ascending order
        @param list1d to be sorted
        @returns the sorted list as an 1D array
        @raises ValueError if the list is None
        """
        if list1d is None: raise ValueError('List mustn\'t be None')
        if len(list1d) in [0, 1]: return list1d

        for b in range(self.base): #for each bucket
            for n in list1d: #for every number of the input list
                digit = (n // (10 ** b)) % 10 #get last digit from the end for the first bucket (b=0), second last digit for second bucket (b=1) and so on
                self.buckets[b][digit].append(n) #append the number to the corresponding sub-bucket based on the relevant digit

            list1d = self.itertools_chain_from_iterable(self.buckets[b]) #merge all the sub-buckets to get the list of numbers sortd by the corresponding digit

        return list1d


    def itertools_chain_from_iterable(self,arr): 
        return list(chain.from_iterable(arr))

Now, I'm assessing its complexity using the big_o module (knowing that the complexity should actually be O(b*n) with b being the base of the RadixSort, i.e. the max number of digits in the numbers to be sorted, i.e. len(self.buckets == self.base ==b) and n being the number of numbers in the list to be sorted):

print('r.sort complexity:',big_o.big_o(r.sort,
                           lambda n: big_o.datagen.integers(n,1,9999999),
                           n_measures=10)[0])

And the output is as follows:

r.sort complexity: Exponential: time = -2.9 * 0.0001^n (sec)

What am I doing wrong here? I rather tend to think that something about the way I'm using big_o is not correct than that my RadixSort implementation has exponential complexity. Any tips/ideas would be greatly appreciated!

0

There are 0 best solutions below