Question regarding BigO' Notations and time complexity

Dev Shed Forums Sponsor:

November 28th, 2012, 03:10 PM

Nightmareix35

Contributing User

Join Date: Nov 2012

Posts: 32

Time spent in forums: 8 h 42 m 41 sec
Reputation Power: 1

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

b49P23TIvg

Contributing User

Join Date: Aug 2011

Posts: 3,350

Time spent in forums: 1 Month 2 Weeks 3 Days 7 h 38 m 16 sec
Reputation Power: 383

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!

November 28th, 2012, 04:22 PM

Nightmareix35

Contributing User

Join Date: Nov 2012

Posts: 32

Time spent in forums: 8 h 42 m 41 sec
Reputation Power: 1

Quote:

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")

Seems like you're right like always

November 28th, 2012, 04:51 PM

b49P23TIvg

Contributing User

Join Date: Aug 2011

Posts: 3,350

Time spent in forums: 1 Month 2 Weeks 3 Days 7 h 38 m 16 sec
Reputation Power: 383

I wish.

My answer differs from your known answer. How could I be correct?

Question regarding BigO' Notations and time complexity

Developer Shed Advertisers and Affiliates