Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
April 13th, 2013, 07:03 PM
 rozenman
Registered User

Join Date: Apr 2013
Posts: 3
Time spent in forums: 1 h 39 m 58 sec
Reputation 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
April 13th, 2013, 09:39 PM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,216
Time spent in forums: 1 Month 3 Weeks 2 Days 18 h 32 m 42 sec
Reputation Power: 455
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
__________________
[code]Code tags[/code] are essential for python code!

Last edited by b49P23TIvg : April 13th, 2013 at 09:51 PM.

#3
April 14th, 2013, 02:42 AM
 rozenman
Registered User

Join Date: Apr 2013
Posts: 3
Time spent in forums: 1 h 39 m 58 sec
Reputation 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!

#4
April 15th, 2013, 11:31 AM
 b49P23TIvg
Contributing User

Join Date: Aug 2011
Posts: 4,216
Time spent in forums: 1 Month 3 Weeks 2 Days 18 h 32 m 42 sec
Reputation Power: 455
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
 plot.png (11.5 KB, 19 views)

Last edited by b49P23TIvg : April 15th, 2013 at 11:38 AM.

#5
April 15th, 2013, 12:10 PM
 rozenman
Registered User

Join Date: Apr 2013
Posts: 3
Time spent in forums: 1 h 39 m 58 sec
Reputation 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)

 Viewing: Dev Shed Forums > Programming Languages > Python Programming > Question regarding Big O notation