#1
  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. #2
  3. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,854
    Rep Power
    481
    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!
  4. #3
  5. 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
  6. #4
  7. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,854
    Rep Power
    481

    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!

IMN logo majestic logo threadwatch logo seochat tools logo