String functions overview in C++ - Time & Space Complexity

Time Complexity: String functions overview

O(n)

Understanding Time Complexity

When using string functions, it's important to know how their running time changes as the string gets longer.

We want to understand how the cost of these functions grows with the size of the input string.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

#include <string>
#include <iostream>

int main() {
    std::string s = "hello world";
    auto length = s.length();
    auto pos = s.find('o');
    auto substr = s.substr(0, 5);
    s.append("!!!");
    std::cout << substr << std::endl;
    return 0;
}
    

This code uses common string functions: length, find, substr, and append.

Identify Repeating Operations

Look at what each function does repeatedly:

• length(): Checks the stored size, no loop.
• find(): Scans characters until it finds the target.
• substr(): Copies a part of the string, character by character.
• append(): Adds characters to the end, copying them.

The dominant operations are the ones that scan or copy characters.

How Execution Grows With Input

Let's see how the number of operations changes as the string size grows.

Input Size (n)	Approx. Operations for find()	Approx. Operations for substr()
10	Up to 10 checks	Copies up to 5 chars
100	Up to 100 checks	Copies up to 5 chars
1000	Up to 1000 checks	Copies up to 5 chars

Notice that find() grows with the string length, but substr() depends on the substring size, not the whole string.

Final Time Complexity

Time Complexity: O(n)

This means the time to run these string functions grows roughly in direct proportion to the string length.

Common Mistake

[X] Wrong: "All string functions run in constant time regardless of string size."

[OK] Correct: Some functions like find() need to look at many characters, so their time grows with string length. substr() time grows with the substring size.

Interview Connect

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

Self-Check

"What if we changed substr() to copy the entire string instead of a part? How would the time complexity change?"