Алгоритм деления - сложность времени

Question

Может кто-нибудь помочь с временной сложностью этого алгоритма, и почему это O (n ^ 2). Было бы полезно пошаговое объяснение, спасибо!

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)

Answer 1

Из-за рекурсии функцияdiv () вызывается до n раз.

Предположим, что простая арифметика с n-битными целыми числами занимает O (n) времени. (Это верно для всех больших целочисленных реализаций, о которых я знаю - например, в Python добавление 1 к большому целому копирует все это).

Тогда у нас есть конечное число O (n) операций, выполняемых до n раз. Это займет O (n ^ n) времени.

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

Answer 2

Наихудшим случаем, когда каждый бит в x равен 1 (например, 0xffff), является O (n). Хитрость заключается в том, чтобы преобразовать рекурсию в итерацию.