Boolean type in Rust - Time & Space Complexity

Time Complexity: Boolean type

O(n)

Understanding Time Complexity

When working with Boolean values in Rust, it's helpful to understand how fast operations on them run.

We want to know how the time to process Boolean values changes as we use more of them.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn count_true(values: &[bool]) -> usize {
    let mut count = 0;
    for &value in values {
        if value {
            count += 1;
        }
    }
    count
}

This code counts how many true values are in a list of Booleans.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each Boolean in the list.
• How many times: Once for every item in the input list.

How Execution Grows With Input

As the list gets longer, the code checks each Boolean one by one.

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

Pattern observation: The number of operations grows directly with the number of Booleans.

Final Time Complexity

Time Complexity: O(n)

This means the time to count true values grows in a straight line as the list gets longer.

Common Mistake

[X] Wrong: "Checking Booleans is instant no matter how many there are."

[OK] Correct: Even though each check is fast, doing many checks adds up as the list grows.

Interview Connect

Understanding how simple operations like checking Booleans scale helps you explain your code's speed clearly and confidently.

Self-Check

"What if we changed the input to a nested list of Booleans? How would the time complexity change?"