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$
3
  • 1
    $\begingroup$ Please don't repeatedly use such long variables. Just define $b = \text{number of bits}$ and use $b$. $\endgroup$
    – orlp
    Feb 7, 2018 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, 2018 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, 2018 at 7:38

1 Answer 1

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 and acknowledge that you have read and understand our privacy policy and code of conduct.

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