What is the Big O complexity for this division algorithm

Question

Input: Two n-bit integers x and y, where x ≥ 0, y ≥ 1.
Output: The quotient and remainder of x divided by y.
if  x = 0, then return (q, r) := (0, 0);
q := 0;  r := x; 
while (r ≥ y) do
    { q := q + 1;
      r := r – y};
return (q, r);

I have obtained the Big O complexity as O(n^2) but a friends says it is O(2^n) where n is the number of bits as the input size

Please provide explanation

Answer 1

The number of iterations of the while-loop is exactly floor(x/y). Each iteration takes n operations, because that is the complexity of the subtraction r - y.

Hence the complexity of the algorithm is n * floor(x/y). However, we want to express the complexity as a function of n, not as a function of x and y.

Thus the question becomes: how does floor(x/y) relate to n, in the worst case?

The biggest value that can be obtained for x/y when x and y are two nonnegative n-digits numbers, and y >= 1, is obtained by taking the biggest possible value for x, and the smallest possible value for y.

• The biggest possible value for x is x = 2**n - 1 (all bits of x are 1 in its binary representation);
• The smallest possible value for y is y = 1.

Hence the biggest possible value for x/y is x/y = 2**n - 1.

The time-complexity of your division algorithm is O(n * 2**n), and this upper-bound is achieved when x = 2**n - 1 and y = 1.