Hot answers tagged

6

It depends on the model of computation. In the transdichotomous model, which is the standard model in the analysis of algorithms, we assume that the word size is $w=O(\log n)$ bits, where $n$ is the size of input in bits. In this assumption, the sum of the input can be represented with 1 word, so the space complexity is $O(1)$ words. Measured in bits, the ...


2

Resource usage always depends on your model of computation. If you're in a situation where integers can grow arbitrarily large then, yes, you need to take that into account. One way of doing this is by assuming that integer variables take an amount of space that depends on the value stored. Another way is to use something like the word RAM model, which more ...


1

No, breaking the algorithm by increasing n (the amount of numbers) makes this 100% not working in constant space. To the question nobody asked: You could easily modify the algorithm to get the space to be constant. (Only the solution given in the interview has this problem. The "best" solution does not have this problem.) Basically the size of the sum ...


Only top voted, non community-wiki answers of a minimum length are eligible