time-complexity - 除法算法 - 时间复杂度

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

由于递归，divide() 最多被调用 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