String handling basics in C++ - Time & Space Complexity

Time Complexity: String handling basics

O(n)

Understanding Time Complexity

When working with strings, it is important to know how the time to process them changes as the string gets longer.

We want to find out how the time to handle strings grows when the input size increases.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <string>
#include <iostream>

int countVowels(const std::string &s) {
    int count = 0;
    for (char c : s) {
        if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ||
            c == 'A' || c == 'E' || c == 'I' || c == 'O' || c == 'U') {
            count++;
        }
    }
    return count;
}
    

This code counts how many vowels are in a given string by checking each character one by one.

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 string (n times).

How Execution Grows With Input

As the string gets longer, the number of characters to check grows the same way.

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

Pattern observation: The work grows directly with the length of the string.

Final Time Complexity

Time Complexity: O(n)

This means the time to count vowels grows in a straight line as the string gets longer.

Common Mistake

[X] Wrong: "Checking each character is very slow and grows faster than the string length."

[OK] Correct: Actually, the code looks at each character only once, so the time grows just as the string grows, not faster.

Interview Connect

Understanding how string operations scale helps you write efficient code and explain your reasoning clearly in interviews.

Self-Check

"What if we changed the code to check every pair of characters instead of single characters? How would the time complexity change?"