Dynamic Stack Using Resizable Array in DSA C - Time & Space Complexity

Time Complexity: Dynamic Stack Using Resizable Array

O(1) amortized

Understanding Time Complexity

We want to understand how the time to add or remove items from a dynamic stack changes as the stack grows.

How does resizing the array affect the speed of stack operations?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#define INITIAL_CAPACITY 4

typedef struct {
    int *array;
    int capacity;
    int top;
} Stack;

void push(Stack *s, int value) {
    if (s->top == s->capacity) {
        s->capacity *= 2;
        s->array = realloc(s->array, s->capacity * sizeof(int));
    }
    s->array[s->top++] = value;
}

int pop(Stack *s) {
    if (s->top == 0) return -1; // empty
    return s->array[--s->top];
}
    

This code shows a stack that doubles its array size when full, allowing dynamic growth.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Adding or removing one item from the stack.
• How many times: Each push or pop happens once per call, but resizing copies all elements occasionally.

How Execution Grows With Input

Most pushes take a simple step, but when the array is full, it doubles size and copies all items.

Input Size (n)	Approx. Operations
10	About 10 simple pushes + 2 resizes copying 4 and 8 items
100	About 100 pushes + 5 resizes copying 4, 8, 16, 32, 64 items
1000	About 1000 pushes + 8 resizes copying increasing items each time

Pattern observation: Most pushes are fast, but resizing happens rarely and costs more, spreading the cost over many pushes.

Final Time Complexity

Time Complexity: O(1) amortized

This means each push usually takes a quick step, but sometimes a bigger step happens; averaged out, each push is still fast.

Common Mistake

[X] Wrong: "Every push takes a long time because of resizing."

[OK] Correct: Resizing happens only occasionally, so most pushes are quick; the big cost is spread out over many pushes.

Interview Connect

Understanding amortized time helps you explain why dynamic arrays and stacks are efficient in real programs, showing you know how data structures work under the hood.

Self-Check

"What if we shrank the array size when many items are popped? How would that affect the time complexity?"