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(bx/2c,y)

q = 2q, r = 2r

if x is odd: r = r + 1

if r y: r = ry, q = q + 1

return (q,r)

Justify the correctness of the recursive division algorithm and show that it takes time O(n2) on n-bit inputs.