Character Frequency Counting in DSA Python - Time & Space Complexity

Time Complexity: Character Frequency Counting

O(n)

Understanding Time Complexity

Counting how often each character appears in a string is a common task. We want to know how the time it takes grows as the string gets longer.

How does the number of steps change when the input string size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

text = "hello world"
frequency = {}
for char in text:
    if char in frequency:
        frequency[char] += 1
    else:
        frequency[char] = 1
print(frequency)

This code counts how many times each character appears in the given text string.

Identify Repeating Operations

• Primary operation: Looping through each character in the string once.
• How many times: Exactly once for each character, so as many times as the string length.

How Execution Grows With Input

As the string gets longer, the number of steps grows directly with the number of characters.

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

Pattern observation: Doubling the input size roughly doubles the work done.

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: "Checking if a character is in the dictionary inside the loop makes it slower than linear."

[OK] Correct: Dictionary lookups are very fast (average constant time), so they do not add extra growth beyond the loop itself.

Interview Connect

Understanding how simple loops and dictionary lookups work together helps you explain and write efficient code in interviews. It shows you can analyze and predict performance clearly.

Self-Check

"What if we used a nested loop to compare each character with every other character? How would the time complexity change?"