Stack overflow detection in Embedded C - Time & Space Complexity

Time Complexity: Stack overflow detection

O(1)

Understanding Time Complexity

We want to understand how the time needed to detect a stack overflow changes as the program runs.

How does the detection process scale when the stack grows larger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#define STACK_SIZE 100
int stack[STACK_SIZE];
int top = -1;

int push(int value) {
  if (top >= STACK_SIZE - 1) {
    return -1; // Stack overflow detected
  }
  stack[++top] = value;
  return 0;
}
    

This code tries to add a value to a stack and checks if the stack is full to detect overflow.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: A single comparison to check if the stack is full before pushing.
• How many times: Once per push operation, no loops or recursion involved.

How Execution Grows With Input

Each push checks the top index against the stack size once, regardless of how many items are in the stack.

Input Size (n)	Approx. Operations
10	10 comparisons
100	100 comparisons
1000	1000 comparisons

Pattern observation: The number of operations grows directly with the number of push attempts, but each check is simple and constant time.

Final Time Complexity

Time Complexity: O(1)

This means each stack overflow check takes the same small amount of time no matter how big the stack is.

Common Mistake

[X] Wrong: "Checking for stack overflow takes longer as the stack grows."

[OK] Correct: The check only compares the top index to a fixed size, so it always takes the same time.

Interview Connect

Understanding that simple checks like stack overflow detection run in constant time helps you explain efficient code and avoid unnecessary loops.

Self-Check

"What if the stack overflow check involved scanning the entire stack array? How would the time complexity change?"