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

Practice

1. What values can a Rust bool type hold?

easy

A. Only true or false

B. Any number

C. Any string

D. Only 0 or 1

Solution

1. Step 1: Understand the bool type in Rust

   The bool type in Rust is designed to hold only two values: true or false.

2. Step 2: Compare with other options

   Other options like numbers or strings are not valid for bool. Rust does not treat 0 or 1 as boolean values directly.

3. Final Answer:

   Only true or false -> Option A

4. Quick Check:

   Rust bool = true or false [OK]

Hint: Remember: bool means true or false only [OK]

Common Mistakes:

• Thinking bool can hold numbers
• Confusing bool with integers 0 or 1
• Assuming bool can hold strings

2. Which of the following is the correct way to declare a boolean variable in Rust?

easy

A. let is_active: bool = true;

B. bool is_active = true;

C. var is_active = true;

D. let is_active = boolean true;

Solution

1. Step 1: Recall Rust variable declaration syntax

   In Rust, variables are declared with let, and the type follows the variable name with a colon, like let var_name: type = value;.

2. Step 2: Check each option

   let is_active: bool = true; uses correct Rust syntax for a boolean variable. Options B and C use syntax from other languages. let is_active = boolean true; is invalid syntax.

3. Final Answer:

   let is_active: bool = true; -> Option A

4. Quick Check:

   Rust bool variable = let name: bool = value; [OK]

Hint: Use 'let var: bool = true;' to declare booleans [OK]

Common Mistakes:

• Using C-style declarations
• Using 'var' keyword (not Rust)
• Writing 'boolean' instead of 'bool'

3. What will be the output of this Rust code?

fn main() {
    let a = true;
    let b = false;
    println!("{}", a && b);
}

medium

A. true

B. 1

C. false

D. Compilation error

Solution

1. Step 1: Understand the boolean AND operator

   The expression a && b returns true only if both a and b are true. Here, a is true and b is false.

2. Step 2: Evaluate the expression

   Since b is false, a && b evaluates to false. The println! macro prints this value.

3. Final Answer:

   false -> Option C

4. Quick Check:

   true AND false = false [OK]

Hint: AND is true only if both are true [OK]

Common Mistakes:

• Assuming true && false is true
• Confusing boolean with integer 1 or 0
• Expecting compilation error

4. Identify the error in this Rust code snippet:

fn main() {
    let flag: bool = True;
    println!("{}", flag);
}

medium

A. Variable name 'flag' is invalid

B. bool type cannot be assigned directly

C. Missing semicolon after println!

D. 'True' should be lowercase 'true'

Solution

1. Step 1: Check boolean literal case sensitivity

   In Rust, boolean literals are lowercase: true and false. Using True causes a compilation error.

2. Step 2: Verify other syntax

   The variable name is valid, semicolon is present after println!, and bool can be assigned directly.

3. Final Answer:

   'True' should be lowercase 'true' -> Option D

4. Quick Check:

   Rust bool literals are lowercase true/false [OK]

Hint: Use lowercase true/false in Rust [OK]

Common Mistakes:

• Writing True or False with uppercase
• Thinking semicolon is missing
• Confusing variable name rules

5. Given a variable score of type i32, which Rust expression correctly sets passed as a boolean indicating if score is 50 or more?

hard

A. let passed: bool = score > 50 || false;

B. let passed: bool = score >= 50;

C. let passed: bool = if score >= 50 { true };

D. let passed: bool = score == true;

Solution

1. Step 1: Understand boolean expressions with comparisons

   The expression score >= 50 returns a boolean true if score is 50 or more, otherwise false.

2. Step 2: Evaluate each option

   let passed: bool = score >= 50; directly assigns the comparison result to passed. let passed: bool = score > 50 || false; is incorrect because score > 50 || false excludes 50 itself. let passed: bool = if score >= 50 { true }; is invalid because the if lacks an else branch and thus doesn't return a value when the condition is false (compilation error). let passed: bool = score == true; compares an integer to a boolean, which is invalid.

3. Final Answer:

   let passed: bool = score >= 50; -> Option B

4. Quick Check:

   Comparison returns bool, assign directly [OK]

Hint: Use comparison directly to get bool result [OK]

Common Mistakes:

• Using if without an else branch for assignment
• Comparing int to bool directly
• Using wrong comparison operators