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?"

Practice

1. What is a memory leak in C programming?

easy

A. When allocated memory is not freed after use

B. When a program runs out of variables

C. When a program crashes due to syntax errors

D. When memory is allocated too quickly

Solution

1. Step 1: Understand memory allocation

   Memory is allocated dynamically using functions like malloc().

2. Step 2: Identify what causes leaks

   If allocated memory is not freed using free(), it causes a memory leak.

3. Final Answer:

   When allocated memory is not freed after use -> Option A

4. Quick Check:

   Memory leak = not freeing allocated memory [OK]

Hint: Memory leak means forgetting to free allocated memory [OK]

Common Mistakes:

• Confusing memory leak with syntax errors
• Thinking memory leaks happen only on crashes
• Believing memory leaks are about variable count

2. Which of the following is the correct way to free dynamically allocated memory in C?

easy

A. free(ptr);

B. release(ptr);

C. delete(ptr);

D. dispose(ptr);

Solution

1. Step 1: Recall C memory management functions

   C uses malloc() to allocate and free() to release memory.

2. Step 2: Identify correct syntax

   free(ptr); is the standard function to free allocated memory.

3. Final Answer:

   free(ptr); -> Option A

4. Quick Check:

   Use free() to release memory [OK]

Hint: Use free() to release memory allocated by malloc() [OK]

Common Mistakes:

• Using delete which is C++ syntax
• Using non-existent functions like release or dispose
• Forgetting to pass the pointer to free()

3. What will be the output of the following C code snippet?

int *ptr = malloc(sizeof(int));
*ptr = 10;
printf("%d\n", *ptr);
// Missing free(ptr);

medium

A. Runtime crash

B. 10

C. Compilation error

D. 0

Solution

1. Step 1: Analyze memory allocation and assignment

   Memory is allocated and 10 is stored at that location.

2. Step 2: Check output and memory freeing

   printf prints 10 correctly; missing free() causes leak but no output error.

3. Final Answer:

   10 -> Option B

4. Quick Check:

   Output prints stored value despite missing free() [OK]

Hint: Missing free() leaks memory but doesn't affect immediate output [OK]

Common Mistakes:

• Assuming missing free causes crash or wrong output
• Confusing memory leak with runtime errors
• Expecting zero or garbage output

4. Identify the problem in this C code snippet:

char *str = malloc(20);
strcpy(str, "Hello World");
// No free(str) called
str = malloc(30);
strcpy(str, "New String");
free(str);

medium

A. No problem, code is correct

B. Syntax error in strcpy usage

C. Double free error

D. Memory leak due to first malloc not freed

Solution

1. Step 1: Trace memory allocations

   First malloc(20) is assigned to str, then overwritten by second malloc(30).

2. Step 2: Check freeing of memory

   First allocated memory is lost without free, causing memory leak.

3. Final Answer:

   Memory leak due to first malloc not freed -> Option D

4. Quick Check:

   Overwriting pointer without free causes leak [OK]

Hint: Always free old memory before reassigning pointer [OK]

Common Mistakes:

• Thinking strcpy causes syntax error
• Assuming double free without repeated free calls
• Believing code is leak-free because free is called once

5. You have a function that allocates memory for an integer array and returns it. Which practice helps prevent memory leaks when using this function multiple times?

hard

A. Use global variables to store allocated memory

B. Never call free() because the function handles it internally

C. Always call free() on the returned pointer before reassigning it

D. Allocate memory only once and never reuse pointers

Solution

1. Step 1: Understand ownership of allocated memory

   The caller owns the memory returned and must free it to avoid leaks.

2. Step 2: Prevent leaks by freeing before reassignment

   Calling free() before reassigning pointer prevents losing track of allocated memory.

3. Final Answer:

   Always call free() on the returned pointer before reassigning it -> Option C

4. Quick Check:

   Free before reuse prevents leaks [OK]

Hint: Free returned memory before pointer reuse [OK]

Common Mistakes:

• Assuming function frees memory automatically
• Using global variables without freeing
• Avoiding reuse but causing inefficient memory use