Frequency Counter Pattern Using Hash Map in DSA Python - 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 list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def frequency_counter(arr):
    freq = {}
    for item in arr:
        if item in freq:
            freq[item] += 1
        else:
            freq[item] = 1
    return freq

This code counts how many times each item appears in the list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each item in the list once.
• How many times: Exactly once for each item (n times if list size is n).

How Execution Grows With Input

As the list gets bigger, the number of steps grows directly with the number of items.

Input Size (n)	Approx. Operations
10	About 10 checks and updates
100	About 100 checks and updates
1000	About 1000 checks and updates

Pattern observation: The work grows evenly as the list grows; doubling the list doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to count frequencies grows in a straight line with the number of items.

Common Mistake

[X] Wrong: "Checking if an item is in the frequency map takes time proportional to the list size."

[OK] Correct: Hash maps let us check and update counts in constant time, so each check is very fast regardless of list size.

Interview Connect

Knowing how frequency counting works and its time cost helps you solve many problems efficiently and shows you understand key data structures.

Self-Check

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