[Solved] What is the Big O complexity for this division algorithm

by


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.

2

solved What is the Big O complexity for this division algorithm