Stack vs heap in embedded context - Performance Comparison

Time Complexity: Stack vs heap in embedded context

O(1) for stack allocation, O(n) for heap allocation

Understanding Time Complexity

When working with embedded C, knowing how stack and heap memory behave helps us understand how fast our program runs.

We want to see how the time to allocate or free memory changes as the program runs.

Scenario Under Consideration

Analyze the time complexity of memory allocation on stack vs heap.

// Stack allocation example
void func() {
  int arr[100]; // allocated on stack
  // use arr
}

// Heap allocation example
#include 
void func() {
  int* arr = malloc(100 * sizeof(int)); // allocated on heap
  // use arr
  free(arr);
}
    

This code shows two ways to allocate memory: one on the stack and one on the heap.

Identify Repeating Operations

Look at what happens when memory is allocated or freed repeatedly.

• Primary operation: Memory allocation and deallocation
• How many times: Each time func() runs, allocation happens once

How Execution Grows With Input

Allocation on stack is very fast and stays almost the same time regardless of size.

Input Size (n)	Approx. Operations (Stack)	Approx. Operations (Heap)
10	Very few (simple pointer move)	More (search free block)
100	Very few (same as 10)	More (depends on fragmentation)
1000	Very few (same as 10)	Even more (longer search)

Stack allocation time stays almost constant; heap allocation time grows with size and fragmentation.

Final Time Complexity

Time Complexity: O(1) for stack allocation, O(n) for heap allocation

This means stack allocation is very fast and predictable, while heap allocation can take longer as more memory is used.

Common Mistake

[X] Wrong: "Allocating memory on the heap is always as fast as on the stack."

[OK] Correct: Heap allocation involves searching for free space and managing fragmentation, which takes more time than simple stack pointer moves.

Interview Connect

Understanding stack vs heap speed helps you write efficient embedded code and answer questions about memory management clearly.

Self-Check

"What if we used a custom memory pool instead of the standard heap? How would the time complexity of allocation change?"