Frequency Counter Pattern Using Hash Map in DSA C - Time & Space Complexity

Time Complexity: Frequency Counter Pattern Using Hash Map

O(n)

Understanding Time Complexity

We want to understand how fast the frequency counter pattern runs when counting items.

How does the time needed grow as the input list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <stdio.h>
#include <string.h>

void frequencyCounter(char arr[], int freq[], int size) {
    for (int i = 0; i < size; i++) {
        freq[(unsigned char)arr[i]]++;
    }
}

int main() {
    char arr[] = "aabbcc";
    int freq[256] = {0};
    int size = strlen(arr);
    frequencyCounter(arr, freq, size);
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) {
            printf("%c: %d\n", i, freq[i]);
        }
    }
    return 0;
}
    

This code counts how many times each character appears in the input string using a frequency array as a hash map.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Loop over the input array to count frequencies.
• How many times: Exactly once for each character in the input (size times).

How Execution Grows With Input

Each character is counted once, so the work grows directly with input size.

Input Size (n)	Approx. Operations
10	About 10 increments
100	About 100 increments
1000	About 1000 increments

Pattern observation: The number of operations grows in a straight line as input size increases.

Final Time Complexity

Time Complexity: O(n)

This means the time to count frequencies grows directly with the number of items in the input.

Common Mistake

[X] Wrong: "Using a hash map makes counting slower because of extra lookups."

[OK] Correct: Hash maps or arrays let us find and update counts instantly, so counting is still fast and linear.

Interview Connect

Knowing how frequency counting works and its time cost helps you solve many problems efficiently in interviews.

Self-Check

"What if we used a linked list instead of a hash map to count frequencies? How would the time complexity change?"