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

Answer 2

最坏的情况，x 中的每一位都是 1（例如 0xffff），是 O(n)。诀窍是将递归转换为迭代。