I'm struggling to analyze the runtime of this algorithm mainly because it depends on two parameters - the length of the input n, and also the bit size of individual n (bitnum). Most documentation I can find solve recursion based on n solely. The algorithm is:
def sortB(seq,bitnum):
# length of seq
n = len(seq)
lists = []
for j in range(0,256):
lists.append([]);
for i in range(0,n):
bits = (seq[i] >> bitnum) & 255;
#print("bitnum :", bitnum)
#print("seq[i] :", seq[i] >> bitnum)
lists[bits].append(seq[i]);
#print("bits ",bits)
i = 0;
for j in range(0,256):
seqj = [0]*len(lists[j])
k = 0
for m in lists[j]:
seqj[k] = m
k = k + 1
if (bitnum > 0):
bitnum = bitnum - 8
seqj = sortB(seqj, bitnum)
for m in seqj:
seq[i] = m
i = i + 1
return seq
I tried to think about this and basically I get this far:
Because the recursion happens based on the number of times bitnum is decremented by 8 $b = bitnum$
$T(n,b-8)$
I solve the recursion of $T(b) = 256T(b-8)$
and I get T$(b) = 256^{(b/8)}$ which simplifies to $2^{(b)}$
Therefore, the whole algorithm gets multiplied by a factor of $2^{b}$: I get a runtime of $O(2^{b} n)$ which is in $O(n)$? But I feel this is wrong since the upper bound on the running time isn't taking this new factor (b) into account.
not all [interested in CS] know Python
- besides, the code looks a) buggy b) un-pythonic. If you can test (and, if necessary, modify) this to give the result desired, code review can be expected to try and improve coding (explicitly stating looking for most simple, non-idiosyncratic code may help) and comment on everything, including algorithm. $\endgroup$