Counting with boolean arrays in NumPy - Time & Space Complexity

Time Complexity: Counting with boolean arrays

O(n)

Understanding Time Complexity

We want to understand how the time to count True values in a boolean array changes as the array grows.

How does the work needed grow when the array gets bigger?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

import numpy as np

arr = np.random.choice([True, False], size=1000)
count_true = np.sum(arr)
print(count_true)

This code creates a boolean array and counts how many values are True.

Identify Repeating Operations

• Primary operation: Summing all elements in the boolean array.
• How many times: Once over all elements, so the number of elements times.

How Execution Grows With Input

Counting True values means checking each element once.

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

Pattern observation: The work grows directly with the number of elements.

Final Time Complexity

Time Complexity: O(n)

This means the time to count True values grows linearly as the array size grows.

Common Mistake

[X] Wrong: "Counting True values is instant regardless of array size."

[OK] Correct: The program must look at each element at least once to know if it is True or False, so time grows with array size.

Interview Connect

Understanding how counting works helps you explain efficiency clearly and shows you know how data size affects performance.

Self-Check

"What if we used a sparse representation for the boolean array? How would the time complexity change?"