# Runtime analysis of bit sorting algorithm with input size and integer size

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 = *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


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.

• Please don't repeatedly use such long variables. Just define $b = \text{number of bits}$ and use $b$. – orlp Feb 7 '18 at 17:04
• That's a lot of code to read. Also, not all of us here know Python. Can you express that as concise pseudocode? – D.W. Feb 7 '18 at 19:53
• 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. – greybeard Feb 8 '18 at 7:38

If you treat $b$ as a constant, then $O(2^b n)$ is $O(n)$, and $O(n)$ is right.
If $b$ is not a constant, $O(2^b n)$ is not $O(n)$.
I think it would help to review Landau notation. The running time is whatever it is; it is some value $T(n,b)$ that depends on both $n$ and $b$. The big-O notation helps us understand how this value grows as you increase $n$ but hold $b$ fixed, or how it grows as you increase both $n$ and $b$. You have to decide which of those you want to understand (do you want to understand its behavior as you increase $n$ while holding $b$ fixed? do you want to understand how it grows when you increase $b$ while holding $n$ fixed? do you want to understand how it grows when you increase both of them? that will lead to different results and different ways of applying big-O notation).