Anagram Check Techniques in DSA C - Time & Space Complexity

Time Complexity: Anagram Check Techniques

O(n)

Understanding Time Complexity

We want to understand how the time needed to check if two words are anagrams changes as the words get longer.

How does the work grow when input size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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

bool areAnagrams(char *str1, char *str2) {
    int count[256] = {0};
    int i;
    for (i = 0; str1[i] && str2[i]; i++) {
        count[(unsigned char)str1[i]]++;
        count[(unsigned char)str2[i]]--;
    }
    if (str1[i] || str2[i]) return false;
    for (i = 0; i < 256; i++) {
        if (count[i] != 0) return false;
    }
    return true;
}

This code checks if two strings are anagrams by counting character frequencies.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Two loops: one to count characters in both strings, one to check counts.
• How many times: First loop runs once per character until string ends (n times), second loop runs 256 times (constant).

How Execution Grows With Input

The first loop grows with the length of the strings, doing work for each character. The second loop always does the same amount of work (256 checks), no matter the input size.

Input Size (n)	Approx. Operations
10	~10 + 256 = 266
100	~100 + 256 = 356
1000	~1000 + 256 = 1256

Pattern observation: The work grows mostly in a straight line with input size because the first loop depends on string length, while the second loop is constant.

Final Time Complexity

Time Complexity: O(n)

This means the time to check anagrams grows linearly with the length of the strings.

Common Mistake

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

[OK] Correct: The second loop runs a fixed 256 times regardless of input size, so it is constant time and does not multiply with n.

Interview Connect

Understanding how counting characters leads to linear time helps you explain efficient solutions clearly and confidently in interviews.

Self-Check

"What if we sorted both strings first and then compared them? How would the time complexity change?"