April 13th, 2013, 07:03 PM

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!
April 13th, 2013, 09:39 PM

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 09:51 PM.
[code]
Code tags[/code] are essential for python code and Makefiles!
April 14th, 2013, 02:42 AM

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!
April 15th, 2013, 11:31 AM

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 overdetermined
(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
Last edited by b49P23TIvg; April 15th, 2013 at 11:38 AM.
[code]
Code tags[/code] are essential for python code and Makefiles!
April 15th, 2013, 12:10 PM

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)