Does an algorithm that allocates nothing have O(1) space complexity?

Not necessarily, you have to count the call stack. A recursive algorithm that recurses to depth d uses O(d) stack space for the frames, even if it never calls malloc. So a recursion that's n deep (like naive recursive list traversal) is O(n) space, and on an MCU with a few kilobytes of stack that can overflow and corrupt memory. Truly O(1) extra space means constant additional memory regardless of input, an in-place two-pointer reverse, an iterative loop with a fixed set of locals. When analyzing space, count heap allocations and maximum stack depth; the iterative version of an algorithm often turns O(n) stack space into O(1), which is why deep recursion is discouraged in constrained systems.