What does it mean when it is stipulated that extra allowed space is O(1)?

If the depth of the stack (recursion) is constant and does not change with respect to the size of the input, then a recursive solution can be O(1) extra space.

Some compilers may do tail call optimization (TCO) and remove recursive calls if they are the last statement executed in any given code path through a function. With TCO, there is no call-stack related memory overhead.

However, keep in mind that the O(1) constraint may be being imposed to force you to choose a particular (probably non-recursive) algorithm, so relying on tail call optimisation may be unwise even if you know the compiler you are using has made the relevant transformation to your code. At the very least, if you rely on it, you should say so explicitly and justify your expectation that TCO will occur by reference to language specifications, compiler documentation and/or disassembly as appropriate.

extra allowed space is O(1)

means that your program can use only a constant amount of space, say C.

Going by the definition of big-O, this means that the space that your program needs cannot depend on the size of the input, although C can be made arbitrarily large.

So if the recursion depends on the input ^a (which usually is the case), the space that your program needs is not O(1).

To clarify further :

• A program which always uses 1 Mb uses O(1) space.

• A program which always uses 1 Tb is using O(1) space ^b.

• A program which uses N Mb, where N is a part of the input, does not use O(1) space, (it uses O(N) space).

Long story short, whenever you read O(1), just mentally replace it with constant.

---

a. For example, foo(n) = foo(n - 1), the stack space needed here to maintain the function calls is O(n).

b. When material on O notation comments on how the ignored constants can be troublesome, this is what they are talking about.

If the depth of your recursion grows depending on the size of your input (which it usually does), then yes: You would be using an unbounded amount of stack memory. The requirement was to solve the problem with a fixed amount of memory.