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

CodePudding user response：

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.

CodePudding user response：

My proposed solution:

When calculating Big O complexity we need to take n->infinity, where n is > input size, we have 3 possibilities:

1. x & y both become infinity when n->infinity
2. y becomes infinity when n->infinity
3. x becomes infinity when n-> infinity

We are interested only in case 3 here,

(x – i * y ) < y, i being the number of iterations

also written as x/y < i 1

when x becomes infinity LHS(Left hand side) is infinity in this equation which implies RHS is infinity as well

So as n-> infinity the number iterations becomes equal to n

Hence, the complexity is O(n^2)