November 28th, 2012, 03:10 PM

Question regarding BigO' Notations and time complexity
I am given this piece of code, and I have to determine which Big O notation term describes the time complexity of the run time required for this code to complete depending on the size of the input in bits (saying that the input is num = O(2^n)
Could anyone please explain? I know the answer is O(n^2) but I have no way to prove it...
def foo(num):
k=1
while k<=num:
trial_division(k)
k*=2
def trial_division(N):
upper = round(N ** 0.5 + 0.5) # ceiling function of sqrt(N)
for m in range(2,upper+1):
if N % m == 0:
print(m, "is the smallest divisor of", N)
return None
print(N, "is prime")
return None
November 28th, 2012, 04:13 PM

I decided your program should be indented as
Code:
def foo(num):
k=1
while k<=num:
trial_division(k)
k*=2
def trial_division(N):
upper = round(N ** 0.5 + 0.5) # ceiling function of sqrt(N)
for m in range(2,upper+1):
if N % m == 0:
print(m, "is the smallest divisor of", N)
return
print(N, "is prime")
with foo as the main program.
foo repeatedly doubles k, which I think is O(log(num)).
foo calls the trial_division abomination which is runs in at worst O(sqrt(N)) time. I'd multiply the two making overall O(sqrt(num)*log(num)) time. I could be wrong.
[code]
Code tags[/code] are essential for python code and Makefiles!
November 28th, 2012, 04:22 PM

Originally Posted by b49P23TIvg
I decided your program should be indented as
Code:
def foo(num):
k=1
while k<=num:
trial_division(k)
k*=2
def trial_division(N):
upper = round(N ** 0.5 + 0.5) # ceiling function of sqrt(N)
for m in range(2,upper+1):
if N % m == 0:
print(m, "is the smallest divisor of", N)
return
print(N, "is prime")
with foo as the main program.
foo repeatedly doubles k, which I think is O(log(num)).
foo calls the trial_division abomination which is runs in at worst O(sqrt(N)) time. I'd multiply the two making overall O(sqrt(num)*log(num)) time. I could be wrong.
Seems like you're right like always
November 28th, 2012, 04:51 PM

I wish.
My answer differs from your known answer. How could I be correct?
[code]
Code tags[/code] are essential for python code and Makefiles!