这个除法算法的 Big O 复杂度是多少

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);

我得到的 Big O 复杂度为 O(n^2)，但朋友说它是 O(2^n)，其中 n 是作为输入大小的位数

请提供解释

Answer 1

My proposed solution:

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

x & y both become infinity when n->infinity

y becomes infinity when n->infinity

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)

Answer 2

while 循环的迭代次数正好是 floor(x/y)。每次迭代需要 n 次操作，因为那是减法的复杂度 r - y.

因此算法的复杂度为n * floor(x/y)。但是，我们希望将复杂度表示为 n 的函数，而不是 x 和 y.

的函数

因此问题变成：在最坏的情况下，floor(x/y) 与 n 有什么关系？

当x和y是两个非负n位数时，x/y所能得到的最大值，y >= 1是通过取 x 的最大可能值和 y 的最小可能值获得。

x 的最大可能值为 x = 2**n - 1（x 的所有位在其二进制表示中均为 1）；
y 的最小可能值为 y = 1。

因此 x/y 的最大可能值为 x/y = 2**n - 1。

你的除法算法的时间复杂度是O(n * 2**n)，当x = 2**n - 1和y = 1时达到这个上限。

这个除法算法的 Big O 复杂度是多少

What is the Big O complexity for this division algorithm

algorithm

big-o

analysis

time-complexity