Character type in Rust - Time & Space Complexity

Time Complexity: Character type

O(n)

Understanding Time Complexity

When working with characters in Rust, it's important to understand how operations on them scale as input grows.

We want to know how the time to process characters changes when we handle more of them.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

fn count_vowels(text: &str) -> usize {
    let mut count = 0;
    for ch in text.chars() {
        if matches!(ch, 'a' | 'e' | 'i' | 'o' | 'u' |
                         'A' | 'E' | 'I' | 'O' | 'U') {
            count += 1;
        }
    }
    count
}

This function counts how many vowels are in a given text string by checking each character.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each character in the string.
• How many times: Once for every character in the input text.

How Execution Grows With Input

As the text gets longer, the function checks more characters one by one.

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

Pattern observation: The work grows directly with the number of characters; double the text, double the checks.

Final Time Complexity

Time Complexity: O(n)

This means the time to count vowels grows in a straight line with the length of the input text.

Common Mistake

[X] Wrong: "Checking each character is constant time no matter how long the text is."

[OK] Correct: Actually, the function must look at every character, so more characters mean more work.

Interview Connect

Understanding how character processing scales helps you write efficient text handling code, a common task in many programs.

Self-Check

"What if we changed the function to count vowels only in the first half of the text? How would the time complexity change?"