def subtraction_div(dividend: int, divisor: int) -> int:
    if (dividend < 0 and divisor > 0) or (dividend > 0 and divisor < 0):
        sign = -1
    else:
        sign = 1
    dividend = abs(dividend)
    divisor = abs(divisor)
    quotient = 0
    while dividend - divisor > 0:
        quotient  = 1
        dividend -= divisor
    if sign < 0:
        quotient = - quotient
    return quotient

I think the time complexity is O(N) while my CS degree friend lists some hard-to-understand formula to me and telling me it's O(2^N).

CodePudding user response：

n is the number of bits needed to represent the argument, not the largest possible magnitude (which we can call N). N grows exponentially in n, not linearly, and the number of subtractions depends on N. (Ergo, the number of subtractions is exponential in the input size, QED.)

Intuitively, subtraction_div(100, 5) makes 10 times more subtractions than subtraction_div(10, 5), even though the input size is only 1 digit larger. (The number of bits in the binary representation is roughly a constant factor of 3 greater than the number of digits, so we basically ignore the difference between bits and digits when talking about time complexity here.)

You can trivially make the algorithm O(n) by saying that the arguments are provided as base-1 bits strings, so that the bit size and the magnitude are identical, but time complexity is only useful if you restrict yourself to efficient encodings. Any (positive integer) base other than 1 is equivalent to within a constant factor; 2 is generally used because the resulting algorithm descriptions are simpler.

CodePudding user response：

We usually measure the complexity as a function of n, the number of digits in N, which is proportional to log(N).

The worst case is N/1, in which case there are N steps. But N=exp(n), so the complexity is O(N)=O(exp(n)).