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!