Count extra space of a stack
Updated
A stack of n items is Θ(n) extra if it is auxiliary (next-greater, reverse, undo). If the stack IS the structure, that space is the data, not extra. Recursion uses O(depth) call-stack space even with no explicit stack.
What to focus on
Dummy pair fields double constants, still Θ(n). Two stacks for a queue still Θ(n) total items. O(1) extra means a few pointers, not a stack of n.
Worked examples
aux reverse
a = [4, 1, 9], reverse via stack- 3 extra slots
Result: Θ(n) extra
the stack is the data
a = [4, 1, 9] as the ADT- those 3 are the contents
Result: Θ(n) data, O(1) extra pointers
recursion depth
a = [4, 1, 9], fact(n) no explicit stack- n frames
Result: Θ(n) extra on the call stack
Try it
Write extraSpace(kind). kind is "auxReverse", "store", or "recursion". Return extra vs data vs call stack. a = [4, 1, 9], reverse via stack → Θ(n) extra. a = [4, 1, 9] as the ADT → Θ(n) data, O(1) extra pointers. fact(n) no explicit stack → Θ(n) extra on the call stack.
n ≥ 1. The stack or recursion depth is n. Label extra vs data, not underflow.