### Thread: Code complexity - O and Ω notation

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

Join Date
Apr 2017
Posts
36
Rep Power
2

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