Searching and counting elements in Python - Time & Space Complexity

Time Complexity: Searching and counting elements

O(n)

Understanding Time Complexity

When we search and count elements in a list, we want to know how long it takes as the list grows.

We ask: How does the time needed change when the list gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

def count_occurrences(items, target):
    count = 0
    for item in items:
        if item == target:
            count += 1
    return count

This code counts how many times a target value appears in a list.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each item in the list one by one.
• How many times: Once for every item in the list.

How Execution Grows With Input

As the list gets bigger, the code checks more items, so the time grows steadily.

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

Pattern observation: The number of checks grows directly with the list size.

Final Time Complexity

Time Complexity: O(n)

This means the time to count grows in a straight line as the list gets bigger.

Common Mistake

[X] Wrong: "Counting happens instantly no matter how big the list is."

[OK] Correct: The code must look at each item to count, so bigger lists take more time.

Interview Connect

Understanding how searching and counting scales helps you explain your code clearly and shows you know how programs behave with bigger data.

Self-Check

"What if we stopped counting as soon as we found the first target? How would the time complexity change?"