algoritmo de división - tiempo de complejidad

Question

¿Alguien puede ayudar con el tiempo la complejidad de este algoritmo, y por qué es O (n ^ 2). Una explicación paso a paso sería de gran ayuda, gracias!

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

Debido a la recursión, dividir () se llama hasta n veces.

Supongamos aritmética simple en números enteros de n bits toma tiempo O (n). (Esto es cierto en todas las grandes implementaciones enteros que conozco -. En Python, por ejemplo, la adición de 1 a unos grandes ejemplares enteros toda la cosa)

Entonces tenemos un número finito de operaciones O (n) que suceden hasta n veces. Esto toma tiempo 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

El peor de los casos, en donde cada bit en x es 1 (por ejemplo 0xffff), es O (n). El truco es convertir la recursividad en una iteración.