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

Question

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.

Answer 1

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).