# Tag Info

0

Let's take alternative chess. The rules are identical to chess, except that White can pass in it's very first move (but Black can't, even if White passed). Now it's obvious that White has a strategy to never lose. Because if every move except a pass leads to a loss, then White can pass, and we know that whatever move Black does will lead to a loss for ...

1

Maybe it is worth mentioning why some kind of reasoning like White has a winning strategy because everything black does, white could have done before. does not work. You might already be familiar with Zugzwang, i.e. a position where the one who has to move loses (the game or just material) or at least weakens his position. The Trébuchet position shows ...

1

This is unknown at the time of writing. Further, according to solving chess on Wikipedia, no resolution is expected in the near future.

2

It is $O(n)$ and, more precisely, $\Theta(n)$. What might be confusing you is the fact that the length of the encoding of the parameter $n$ will only be $\Theta(\log n)$, meaning that the value of $n$ (and hence the space required by the function) is exponentially larger than the size of the input to function (i.e., the number of bits needed to represent $n$...

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 ...

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 ...

3

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 ...

Top 50 recent answers are included