Character Frequency Counting in DSA C - Time & Space Complexity

Time Complexity: Character Frequency Counting

O(n)

Understanding Time Complexity

We want to understand how long it takes to count how often each character appears in a string.

The question is: how does the time needed grow as the string gets longer?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

void countFrequency(char *str) {
    int freq[256] = {0};
    int i;
    for(i = 0; str[i] != '\0'; i++) {
        freq[(unsigned char)str[i]]++;
    }
    for(i = 0; i < 256; i++) {
        if(freq[i] != 0) {
            printf("%c: %d\n", i, freq[i]);
        }
    }
}

int main() {
    char str[] = "hello world";
    countFrequency(str);
    return 0;
}
    

This code counts how many times each character appears in the input string and prints the counts.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The first loop goes through each character in the string once.
• How many times: It runs once for every character in the input string (n times).
• The second loop runs 256 times, which is a fixed number, not depending on input size.

How Execution Grows With Input

As the string gets longer, the first loop runs more times, directly matching the string length.

Input Size (n)	Approx. Operations
10	About 10 times for the first loop + 256 for the second
100	About 100 times for the first loop + 256 for the second
1000	About 1000 times for the first loop + 256 for the second

Pattern observation: The main work grows directly with the string length, while the second loop stays the same.

Final Time Complexity

Time Complexity: O(n)

This means the time to count characters grows in a straight line with the string length.

Common Mistake

[X] Wrong: "The second loop over 256 characters makes this O(n * 256) which is O(n²)."

[OK] Correct: The second loop runs a fixed 256 times, no matter how big the input is, so it does not multiply with n.

Interview Connect

Counting character frequency efficiently is a common task that shows you understand loops and arrays well.

Knowing how time grows helps you explain your code clearly in interviews.

Self-Check

"What if we used a linked list to store frequencies instead of an array? How would the time complexity change?"