1
$\begingroup$

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.

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.