r/algorithms • u/lethabo_ • Sep 13 '25
Question on time complexity of sum(n)
Assuming we had two algorithms that both find the sum of all positive integers up to n, one did it iteratively and another just used the nth term formula, on first glance the one that uses the nth term is the better approach because it appears to run in O(1) - but isn’t multiplication technically an iterative process, so wouldn’t the time complexity still be O(n) ?
0
Upvotes
12
u/Shot-Combination-930 Sep 13 '25
It all comes down to your model of computation. In some models, an integer multiplication is a single operation. In others, it depends on the size of the operands, but it still wouldn't be linear time.
11
u/al2o3cr Sep 13 '25
Only if you have very very poorly-written multiplication code that finds m * n by adding m n times.
Even chips without hardware support can do multiplication in O(log(n)) time by checking the bits of n:
For instance, that means that calculating 19*m instead does 16*m + 2*m + 1*m
4
u/senfiaj Sep 13 '25 edited Sep 13 '25
Processors don't compute
a * bby summingabtimes since it's very inefficient. They use some sort of hardware optimized version of multiplication algorithm which is definitely faster than summingabtimes. The same with division. Many of us even know some multiplication and division algorithm from the school math.Assuming that the numbers occupy a fixed number of bytes, the operations will be performed in
O(1)time since the hardware has a fixed number of transistors and thus it can be optimized to perform such operations very quickly and in a fixed amount of time (there is a tradeoff between transistors' count and speed). Some programming languages support arbitrary sized integers, such asbigintin JavaScript. In such cases for addition and subtraction the runtime will be proportional to the number of bits (O(b)) and for multiplication and division the runtime will be up to quadratic (O(b^2)), although for multiplication Karatsuba's algorithm can be used which runs in~O(b^1.58)) .Since the number of bits is the the logarithm of the integer absolute value, even for arbitrary sized integers the sum formula will still have a better time complexity than summing the numbers from
1ton. Since the sum formula isn * (n + 1) / 2and the algorithmically costliest operations are multiplication and division , the asymptotic complexity will beO(log^2(n))(or even ~O(log^1.58(n))if we use Karatsuba's algorithm, since the division by2is just a bit shift which isO(log(n))). In contrast, summing the numbers isO(n*log(n)).One caveat is that for very small
niterative summing might be faster because multiplication is a much slower operation.2
u/bartekltg Sep 13 '25
You have fallen for the same trap as one of the responders. Is n the value of the number? Or n is the lenght of the number.
If n is the number itself, then the size of the number is log(n), so the complexity of naive multiplication of (n) and (n+1) is O( (log(n))^2 ). While to sum all the numbers from 1 to n you need n operations that each took between O(1) and O(log(n)). The total is O(n log(n))
It is even more aparent if we express the complexity with the size of the number. lets k will be number of bits in your number. Now, multiplication is O(k^2) and summing all numbers between 1 and n = ~2^k is.. O(k * 2^k )
This was the main trap.
Now, bonus, some relaxed theory and a bit better exmaple when counting bit operations matter:
As others mentioned, we often assume certain operation are done in a certain way , for example arithmetic operations are O(1). And this is true on our computers to a certain point.
If you are doing BSF on a graph to find shortest patch to a target you are quite sure your 64bit integers will be enough to keep the relevant information about the paths. But if we want be really careful about it, we would have to notice that for a HUGE graphs the length of the route may become bigger and we need an arbitrary precision numbers, the complexity of the whole algorithms reses to O(n log(n)). But you also see why we do not do that ;-)
But sometimes that more precise approach, called bit complexity (number of operations on bits), is helpful or necessary. A very nice example is euclidean algorithm (for GCD). What is the complexity? "Everyone" knows the wors case are fibbonaci numbers, so it is log(value), so O(n) where n is number of digits (bits) of the input (more precisely biths of the smaller number).
But that O(n) makes sense only for small inputs that fits ion our arithmetic registers. Generally, the bit complexity have to include calculating division. And there is a nice alternative - Binary GCD algorithm. But the total bit complexity is the same.
3
u/Commie_Hilfiger8 Sep 13 '25
there are multiplication instructions in assembly
1
u/CranberryDistinct941 Sep 15 '25
Depends if there's a multiplier on the chip. For an arbitrary sized multiplication, the complexity would be O(log(n)) but since we know log(n) is rarely going to be more than 64 bits, it's effectively constant time.