algorithmrecursioncomplexity-theoryasymptotic-complexity

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


If the above condition in a programming question is given and I am solving it using recursion then am I violating the constraints? It could be because recursion also uses stack? Is it right?


Solution

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