Double Ended Queue Deque in DSA C - Time & Space Complexity

Time Complexity: Double Ended Queue Deque

O(1)

Understanding Time Complexity

We want to understand how fast operations on a double ended queue (deque) run as the number of items grows.

Specifically, how does adding or removing items from either end affect the time it takes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Simple deque operations
void pushFront(Deque* dq, int val) {
    // Add val at front
    dq->front = (dq->front - 1 + dq->capacity) % dq->capacity;
    dq->arr[dq->front] = val;
    dq->size++;
}

int popBack(Deque* dq) {
    // Remove from back
    int val = dq->arr[(dq->front + dq->size - 1) % dq->capacity];
    dq->size--;
    return val;
}
    

This code adds an item at the front and removes an item from the back of a deque implemented with a circular array.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Simple index calculations and direct array access.
• How many times: Each operation runs once per call, no loops or recursion inside.

How Execution Grows With Input

Each push or pop does a fixed number of steps regardless of how many items are in the deque.

Input Size (n)	Approx. Operations
10	5-6 steps
100	5-6 steps
1000	5-6 steps

Pattern observation: The number of steps stays the same no matter how big the deque is.

Final Time Complexity

Time Complexity: O(1)

This means adding or removing items from either end takes the same short time no matter how many items are stored.

Common Mistake

[X] Wrong: "Removing from the back of a deque takes longer as it gets bigger because you have to shift items."

[OK] Correct: The deque uses a circular array with index math, so no shifting is needed. Each remove or add is a quick step.

Interview Connect

Knowing that deque operations run in constant time shows you understand efficient data structures, a key skill in coding interviews and real projects.

Self-Check

"What if the deque was implemented using a linked list instead of an array? How would the time complexity change?"