#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2013
    Posts
    3
    Rep Power
    0

    Question regarding Big O notation


    Hey guys,
    I got homework - finding out what's the complexity of this code, while 'n' is the number of bits in the number 'num':

    Code:
    import random
    def ohhh(num):
        k=1
        while k<=num:
            trial_division(k)
            r = random.randrange(0,10)
            k = 2*k + r
    
    
    def trial_division(N):
        """ trial division for integer N """
        upper = round(N ** 0.5 + 0.5) # ceiling function of sqrt(N)
        for m in range(2,upper+1):
            if N % m == 0: # m divides N
                print(m, "is the smallest divisor of", N)
                return None
        # we get here if no divisor was found
        print(N, "is prime")
        return None
    So... I need to write the complexity for 2 cases:
    Worst case and best case.
    I can see the best case is that after adding the random number we always get an even number (then the trial_division func is O(1) ), and that the worst case is that we will get as many prime numbers as we can.
    What I was thinking is that:
    Best case - first loop (in ohhh func) is log(n) (base 2). Second func is O(1) - so total of O(log(n))
    Worst case - first loop is log(n) again. Second func is sqrt(n) - so total of O(sqrt(n) * log(n) ).
    I really have no idea if I am wrong... would appreciate some help..
    Thanks!
  2. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,696
    Rep Power
    480
    I cheated. I collected data and fit a curve to both log(N) and sqrt(N) log(N)
    log(N) fits well.
    Here are primes with increasing bit counts.
    PRIMES = (2,5,11,17,37,67,131,257,521,1031,2053,4099,8209,16411,32771,65537,131101,262147,524309,1048583,2097 169,4194319,8388617,16777259,33554467,67108879,134217757,268435459,536870923)

    primes generated in j www.jsoftware.com with sentence

    [&.:(p:inv)2x^>:i.30
    Last edited by b49P23TIvg; April 13th, 2013 at 08:51 PM.
    [code]Code tags[/code] are essential for python code and Makefiles!
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2013
    Posts
    3
    Rep Power
    0
    EDIT:
    nvm, I found out that for the worst case it is O(sqrt(N)) - which might look like log(N)...
    If you count the number of times the inner loop is done, you get the sum of a geometric sequence, that after using the known formula you get sqrt(N).
    For best case it is log(N) as we said before.

    Thanks for the help!
  6. #4
  7. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,696
    Rep Power
    480
    Code:
    def ohhh(num, L):
        k=1
        inner_sum = 0
        while k<=num:
            inner_sum += trial_division(k, L)
            k = 2*k
        return inner_sum
    
    def trial_division(N, L):
        upper = round(N ** 0.5 + 0.5) # ceiling function of sqrt(N)
        for m in range(2,upper+1):
            L[0] += 1  ################ count the number of divisions
            if N % m == 0: # m divides N
                None
        return upper
    
    print('#bits  #divisions')
    L = [0]
    for bits in range(35):
        L[0] = 0
        JUNK = ohhh(2**bits, L)
        print(bits+1, L[0])
    
    # giving this transposed result for bits and divisions
    #1 2 3 4 5  6  7  8  9 10 11  12  13  14  15  16  17   18   19   20   21   22   23   24    25    26    27    28    29    30     31     32     33     34     35
    #1 2 3 5 8 13 20 31 46 68 99 144 207 297 424 605 860 1222 1733 2457 3480 4928 6975 9871 13966 19758 27949 39534 55917 79087 111854 158194 223729 316410 447481
    The following analysis shows, because the correlation coefficient is closer to 1, that O(log(N)) fits better than O(sqrt(N)). A plot of the log of the count of divisions versus the line fit to same shows that the curve is less steep than log(N).

    In executable Iverson notation in which a power table is two characters long and singular value decomposition are each two characters long,
    Code:
    NB. definitions
    times =: *
    log=: ^.
    sqrt =: %:
    evalPolynomial =: p.
    powerTable =: ^/
    svd =: %.  NB. matrix division, svd when the system is over-determined
    
       (log Y) svd powerTable&0 1 X  NB. coefficients of linear fit to the log of Y
    0.32449 0.368423
    
       (log Y) corr 0.32449 0.368423 evalPolynomial X  NB. correlation coefficient of the log fit
    0.99855
    
    
       (sqrt Y) svd powerTable&0 1 X  NB. coefficients of linear fit to the sqrt of Y
    _130.483 13.8891
       
       (sqrt Y) corr _130.483 13.8891 evalPolynomial X  NB. correlation coefficient of the sqrt fit
    0.818733
    Attached Images
    Last edited by b49P23TIvg; April 15th, 2013 at 10:38 AM.
    [code]Code tags[/code] are essential for python code and Makefiles!
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Apr 2013
    Posts
    3
    Rep Power
    0
    I also did a graph (can't upload as I am considered as a new user). I checked how many times the inner loop runs for different inputs (from 2 to 5**5). Had log(N) and sqrt(N) also. I can see that it is almost exactly as sqrt(N)*3.5 which means it is O(sqrt(N) ), while log(N), which is much smaller than sqrt(N), really falls behind...
    Oh, but I did make 1 mistake, when I say N I mean the number 'num' and when I say n I mean the bits - meaning N = O(2^n). That being said, we get for worst case sqrt(2^n) = 2^(n/2)

IMN logo majestic logo threadwatch logo seochat tools logo