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

    Join Date
    Apr 2017
    Posts
    24
    Rep Power
    0

    Code complexity - O and Ω notation


    Sorry for my off topic question (this question is about complexity theory - not about C,
    I couldn't find a subforum for theory).

    For the following code, determine the nearest upper bound of complexity (O) and the nearest lower bound
    of complexity (Ω), if data is given by the following table (see image).
    It is known that in the worst case the condition is satisfied in most cases.



    Could someone describe the procedure for finding the nearest upper bound and the nearest lower bound of complexity,
    or give a reference for this type of problems?

    Note that this is not homework, I am practicing for exam.
  2. #2
  3. Contributing User
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    Aug 2011
    Posts
    5,860
    Rep Power
    509

    Failed the exam.


    C forum is correct for this question.

    Is it a trick question? If n is initially non-negative then the i>=0 test in
    for (int i = n; i >= 0; i /= 2)
    is always true, and the code runs forever.

    Assuming the for statement instead reads for (int i = n; i > 0; i /= 2) { block } leads to interesting experiments I should have done 35 years ago. This code implements timing and timed functions with argument N.

    Code:
    #! /usr/bin/python3 p.py
    # python3 p.py
    
    import time
    import math
    
    tests = 20
    interval = 1e-4
    
    def delay(n):
        time.sleep(max(0, n * interval))
    
    def timeit(f, n):
        start = time.time()
        f(n)
        finish = time.time()
        return n, finish - start
    
    O1 = lambda n: delay(1)
    On = lambda n: delay(n)
    Onn = lambda n: delay(n*n)
    Ologn = lambda n: delay(math.log(n))
    Olognlogn = lambda n: delay(math.log(n)**2)
    
    def main(f, n):
        print('{:-6d}{:12.5f}'.format(*timeit(f, n)))
    
    
    
    if False:  # change to True to run examples
        print('constant  O(1)')
        for i in range(tests):
            main(O1,2**i)
    
        print('linear    O(N)')
        for i in range(tests):
            main(On,2**i)
    
        # fit coefficients for a cubic equation:
        # 7.00935e_5 1.31159e_7 0.000100097 1.29142e_11
        # fit coefficients for the full cubic and log and log squared verb
        #
        # constant   time^1       time^2     time^3     log(time)  log(time)^2
        # 5.87413e_5 8.78606e_6 0.000100031 1.83809e_10 1.03997e_5 _1.83122e_5
        #
        # Is that not cool, the coefficient of the squared term is the interval
        # specifically fitting the measured time (output column 2) as some function of n (column 1)
        print('squared   O(N*N)')
        for i in range(tests):
            main(Onn,2**i)
    
        # 3.65133e_5 _2.83174e_6 3.48047e_8 _1.44766e_10 0.000125548
        # fit to C0 + C1 N + C2 N^2 + C3 N^3 + C4 log(N)
        print('log   O(log(N))')
        for i in range(tests):
            main(Ologn,2**i)
    
        # fit to C0 + C1 N + C2 N^2 + C3 N^3 + C4 log(N) + C5 log(N) log(N)
        # 6.74247e_5 _4.51984e_5 4.87188e_6 _1.32843e_8 1.28346e_11 0.00011006
        print('log squared   O(log(N)^2)')
        for i in range(tests):
            main(Olognlogn,2**(i+2))
    
    
    O = (Ologn, On,)
    omega = (O1, Olognlogn,)
    
    def code(n, slow: bool):
        (f, g,) = O if slow else omega
        i = n
        while i:
            f(i), g(i)
            if slow:
                f(i), f(i), f(i) # ???????????
            i //= 2
    
    Ocode = lambda n: code(n, True)
    omegacode = lambda n: code(n, False)
    
    
    print('worst case code')
    for i in range(tests):
        main(Ocode,int(1.42**(i+8)))
    
    
    print('best case code')
    for i in range(tests):
        main(omegacode,int(1.42**(i+10)))
    
    
    
    '''
       NB.   N     t (O)       t(omega)
       D=:|:".;._2[0 :0
            16     0.00724     0.00415
            23     0.00885     0.00490
            33     0.01247     0.00652
            47     0.01572     0.00747
            67     0.02145     0.00896
            95     0.02687     0.01080
           135     0.03700     0.01267
           192     0.04952     0.01447
           273     0.06889     0.01678
           388     0.09262     0.01915
           551     0.12747     0.02221
           782     0.17393     0.02442
          1111     0.24326     0.02811
          1577     0.33817     0.03165
          2240     0.47197     0.03561
          3181     0.66211     0.03982
          4517     0.93338     0.04433
          6415     1.31310     0.04991
          9109     1.85724     0.05483
         12935     2.62451     0.05979
    )
         16      23      33      47      67      95     135     192     273     388     551     782    1111    1577    2240    3181    4517    6415    9109   12935
    0.00724 0.00885 0.01247 0.01572 0.02145 0.02687   0.037 0.04952 0.06889 0.09262 0.12747 0.17393 0.24326 0.33817 0.47197 0.66211 0.93338  1.3131 1.85724 2.62451
    0.00415  0.0049 0.00652 0.00747 0.00896  0.0108 0.01267 0.01447 0.01678 0.01915 0.02221 0.02442 0.02811 0.03165 0.03561 0.03982 0.04433 0.04991 0.05483 0.05979
    
    
       NB. N^0 1 2
       [P=:^/&(i.3){.D
    1    16       256
    1    23       529
    1    33      1089
    1    47      2209
    1    67      4489
    1    95      9025
    1   135     18225
    1   192     36864
    1   273     74529
    1   388    150544
    1   551    303601
    1   782    611524
    1  1111 1.23432e6
    1  1577 2.48693e6
    1  2240  5.0176e6
    1  3181 1.01188e7
    1  4517 2.04033e7
    1  6415 4.11522e7
    1  9109 8.29739e7
    1 12935 1.67314e8
    
       NB. ln(N)^0 1 2 3
       [L=:^/&(i.4)^.{.D
    1 2.77259 7.68725 21.3136
    1 3.13549 9.83132 30.8261
    1 3.49651 12.2256 42.7468
    1 3.85015 14.8236 57.0732
    1 4.20469 17.6794 74.3366
    1 4.55388 20.7378 94.4374
    1 4.90527 24.0617 118.029
    1  5.2575 27.6413 145.324
    1 5.60947 31.4662 176.509
    1 5.96101 35.5336 211.816
    1 6.31173  39.838 251.447
    1 6.66185 44.3803 295.655
    1 7.01302 49.1824 344.917
    1 7.36328 54.2179 399.221
    1 7.71423 59.5094 459.069
    1 8.06495 65.0434 524.572
    1  8.4156 70.8224 596.013
    1 8.76639 76.8497 673.694
    1 9.11702   83.12 757.807
    1 9.46769 89.6372 848.657
    
       NB. best fit coeffients for time dependent on N.
       NB.   O               omega        term          in plain English
       16j6":(|:}.D)%. >P ([: ,"2 [: */L:_1 {@:,&<"1) L
           _8.494248        0.256755      N^0 log(N)^0  constant
          _11.855245    **  0.113556      N^0 log(N)^1  ln(N)
           _0.116154        0.042572      N^0 log(N)^2  ln(N)^2
           _0.886493        0.007596      N^0 log(N)^3  ln(N)^3
       **  11.757961       _0.224880      N^1 log(N)^0  linear
           _4.176025    **  0.086708      N^1 log(N)^1  linear * ln(N)
            0.546471       _0.012387      N^1 log(N)^2  linear * ln(N)^2
           _0.028086        0.000714      N^1 log(N)^3  linear * ln(N)^3
            0.004977       _0.000196      N^2 log(N)^0  quadratic
           _0.001091        0.000044      N^2 log(N)^1  quadratic * ln(N)  
            0.000082       _0.000003      N^2 log(N)^2  quadratic * ln(N)^2
           _0.000002        0.000000      N^2 log(N)^3  quadratic * ln(N)^3
    '''
    Graphing the data shows O(N) looks linear and agrees with the large positive (11.76) linear term coefficent.
    Omega(N), when plotted as N*ln(N) against measured time looks straight.
    Graphical methods told more than guessing about the size of the fit coefficients.

    Justification based on the program:
    O(N): The outer loop runs in time ln(N). The dominant inner loop is g, which runs in O(N). The product is N ln(N). Not a match!
    Omega(N ln(N)): outer loop ln(N). Inner dominant ln(N)^2. Product is ln(N)^3. Not a match!
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo