Stack Implementation Using Array in DSA C - Time & Space Complexity

Time Complexity: Stack Implementation Using Array

O(1)

Understanding Time Complexity

We want to understand how fast stack operations run when using an array.

Specifically, how does the time to push or pop items change as the stack grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

void push(int x) {
  if (top == MAX - 1) return; // stack full
  stack[++top] = x;
}

int pop() {
  if (top == -1) return -1; // stack empty
  return stack[top--];
}
    

This code shows how to add (push) and remove (pop) items from a stack using an array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Single assignment or retrieval in array for push and pop.
• How many times: Each push or pop does this once, no loops involved.

How Execution Grows With Input

Each push or pop does a fixed number of steps regardless of stack size.

Input Size (n)	Approx. Operations
10	1 operation per push or pop
100	1 operation per push or pop
1000	1 operation per push or pop

Pattern observation: The time does not increase as the stack grows; it stays constant.

Final Time Complexity

Time Complexity: O(1)

This means each push or pop takes the same short time no matter how many items are in the stack.

Common Mistake

[X] Wrong: "Push or pop takes longer as the stack gets bigger because the array is bigger."

[OK] Correct: The code accesses only one position in the array each time, so the size does not affect the time.

Interview Connect

Knowing that stack operations are very fast and constant time helps you explain why stacks are useful in many programs.

Self-Check

"What if we used a linked list instead of an array for the stack? How would the time complexity change?"