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?"

Practice

1. Which Python operator checks if an element exists in a list?

easy

A. in

B. count()

C. find()

D. exists()

Solution

1. Step 1: Understand the purpose of in

   The in operator checks if an element is present in a list or other collection.

2. Step 2: Compare with other options

   count() counts occurrences, find() and exists() are not valid list operators in Python.

3. Final Answer:

   in -> Option A

4. Quick Check:

   Use in to check membership [OK]

Hint: Use in to check presence quickly [OK]

Common Mistakes:

• Confusing count() with membership check
• Using non-existent methods like find()
• Trying to use exists() which is invalid

2. Which of the following is the correct syntax to count how many times the number 5 appears in list nums?

easy

A. count(nums, 5)

B. nums.count(5)

C. nums.count = 5

D. nums.count[5]

Solution

1. Step 1: Identify the correct method call

   To count occurrences, use the list method count() with the element as argument: nums.count(5).

2. Step 2: Check syntax of other options

   count(nums, 5) is invalid syntax, nums.count = 5 assigns a value incorrectly, and nums.count[5] is invalid indexing.

3. Final Answer:

   nums.count(5) -> Option B

4. Quick Check:

   Use list.count(element) to count [OK]

Hint: Use list.count(value) to count occurrences [OK]

Common Mistakes:

• Using function call syntax incorrectly
• Assigning instead of calling method
• Using square brackets instead of parentheses

3. What is the output of this code?

fruits = ['apple', 'banana', 'apple', 'cherry']
print(fruits.count('apple'))

medium

A. Error

B. 1

C. 3

D. 2

Solution

1. Step 1: Understand the list contents

   The list fruits contains 'apple' twice, 'banana' once, and 'cherry' once.

2. Step 2: Apply count() method

   fruits.count('apple') counts how many times 'apple' appears, which is 2.

3. Final Answer:

   2 -> Option D

4. Quick Check:

   Counting 'apple' in list = 2 [OK]

Hint: Count returns how many times item appears [OK]

Common Mistakes:

• Counting unique items instead of occurrences
• Expecting index instead of count
• Confusing count with length

4. Find the error in this code that tries to count how many times 10 appears in numbers:

numbers = [10, 20, 10, 30]
count = numbers.count[10]
print(count)

medium

A. Using square brackets instead of parentheses for count method

B. Variable name 'count' is reserved and cannot be used

C. List 'numbers' is not defined

D. Missing import for count function

Solution

1. Step 1: Identify method call syntax

   Methods in Python are called with parentheses, not square brackets. numbers.count[10] is invalid syntax.

2. Step 2: Correct the syntax

   It should be numbers.count(10) to count occurrences of 10.

3. Final Answer:

   Using square brackets instead of parentheses for count method -> Option A

4. Quick Check:

   Method calls need parentheses, not brackets [OK]

Hint: Use parentheses () to call methods, not brackets [] [OK]

Common Mistakes:

• Using [] instead of () for method calls
• Thinking count is a function needing import
• Assuming variable names are reserved

5. Given a list data = [0, 1, 2, 0, 3, 0, 4], which code snippet counts how many zeros are in the list and prints a message only if zeros exist?

hard

A. if 0 not in data:
print(f\"Zeros found: {data.count(0)}\")

B. print(f\"Zeros found: {data.count(0)}\")

C. if data.count(0) > 0:
print(f\"Zeros found: {data.count(0)}\")

D. if data.contains(0):
print(f\"Zeros found: {data.count(0)}\")

Solution

1. Step 1: Understand the goal

   We want to count zeros and print only if there is at least one zero.

2. Step 2: Analyze each option

   if 0 not in data:
       print(f\"Zeros found: {data.count(0)}\")

   checks if 0 is NOT in data, printing only when NO zeros -- incorrect.

   print(f\"Zeros found: {data.count(0)}\")

   always prints, even if count is zero.

   if data.count(0) > 0:
       print(f\"Zeros found: {data.count(0)}\")

   checks if count > 0 then prints the count. Correct and efficient.

   if data.contains(0):
       print(f\"Zeros found: {data.count(0)}\")

   uses invalid contains().

3. Step 3: Choose best option

   if data.count(0) > 0:
       print(f\"Zeros found: {data.count(0)}\")

   is correct, checking count once and printing only if zeros exist.

4. Final Answer:

   if data.count(0) > 0: print(f\"Zeros found: {data.count(0)}\") -> Option C

5. Quick Check:

   Check count > 0 before printing [OK]

Hint: Check count > 0 to confirm presence before printing [OK]

Common Mistakes:

• Using invalid method contains()
• Printing count without checking if zero exists
• Using not in which prints when zeros are absent