CODEWITHSUNDEEP
time-complexity
KP65
KP65

Reputation: 13585

Divide algorithm - time complexity

Can anyone help with with the time complexity of this algorithm, and why it is O(n^2). A step by step explanation would be helpful, thanks!

function divide(x,y)
    Input: Two n-bit integers x and y, where y >= 1
    Output: The quotient and remainder of x divided by y

    if x = 0:
        return (q,r) = (0,0)

    (q,r) = divide(x/2, y)
    q = 2q
    r = 2r

    if x is odd:
        r = r + 1

    if r >= y:
        r = r - y
        q = q + 1

    return (q,r)

Upvotes: 3

Views: 4388

Answers (2)

splicer
splicer

Reputation: 5394

The worst case, where every bit in x is 1 (e.g. 0xffff), is O(n). The trick is to convert the recursion into an iteration.

Upvotes: 1

Jason Orendorff
Jason Orendorff

Reputation: 45086

Due to the recursion, divide() is called up to n times.

Suppose simple arithmetic on n-bit integers takes O(n) time. (This is true in all the big integer implementations I know about -- in Python, for example, adding 1 to a big integer copies the whole thing.)

Then we have a finite number of O(n) operations happening up to n times. This takes O(n^n) time.

def divide(x, y):
    assert y >= 1
    if x == 0:
        return 0, 0
    q, r = divide(x // 2, y)
    q *= 2
    r *= 2
    if x & 1:
        r += 1
    if r >= y:
        r -= y
        q += 1
    return q, r

Upvotes: 2

Related Questions