Memory leak concepts - Time & Space Complexity

Time Complexity: Memory leak concepts

O(n)

Understanding Time Complexity

When we talk about memory leaks in C, we want to understand how the program's memory use grows over time.

We ask: Does the program keep using more memory as it runs, and how fast does that happen?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

    #include <stdlib.h>
    void leakMemory(int n) {
        for (int i = 0; i < n; i++) {
            int *ptr = malloc(sizeof(int));
            *ptr = i;
            // No free(ptr) here, memory leak occurs
        }
    }
    

This code allocates memory inside a loop but never frees it, causing a memory leak.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Memory allocation with malloc inside a loop.
• How many times: The loop runs n times, so malloc is called n times.

How Execution Grows With Input

Each loop iteration adds a new memory allocation that is never freed.

Input Size (n)	Approx. Memory Allocations
10	10 allocations leaked
100	100 allocations leaked
1000	1000 allocations leaked

Pattern observation: Memory usage grows linearly with n because each iteration leaks one allocation.

Final Time Complexity

Time Complexity: O(n)

This means the number of memory allocations (and leaks) grows directly with the input size.

Common Mistake

[X] Wrong: "Calling malloc inside a loop is always safe because the program runs fast enough."

[OK] Correct: Even if the program runs fast, forgetting to free memory causes leaks that build up and can crash the program or slow it down over time.

Interview Connect

Understanding how memory leaks grow helps you write better C programs and shows you care about resource management, a key skill in programming.

Self-Check

"What if we added a free(ptr) inside the loop? How would the time complexity and memory usage change?"