Divide算法-时间复杂度

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)。诀窍是将递归转换为迭代。