### Thread: Question regarding BigO' Notations and time complexity

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

Join Date
Nov 2012
Posts
32
Rep Power
2

#### 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
2. 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.
3. No Profile Picture
Contributing User
Devshed Newbie (0 - 499 posts)

Join Date
Nov 2012
Posts
32
Rep Power
2
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