Time Complexity: Common string operations
O(n)
0
0
Common string operations - Time & Space Complexity
Understanding Time Complexity
When working with strings in C, it's important to know how the time it takes to run your code changes as the string gets longer.
We want to find out how common string operations grow in cost as the input size grows.
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
#include <string.h>
int length = strlen(str);
char dest[100];
strcpy(dest, str);
int cmp = strcmp(str, dest);
This code finds the length of a string, copies it to another array, and then compares the two strings.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Each function (strlen, strcpy, strcmp) loops through the string characters one by one.
- How many times: Each function runs once, but each checks characters until it finds the string end.
How Execution Grows With Input
As the string gets longer, each operation takes more steps because it looks at every character.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | About 10 steps per operation |
| 100 | About 100 steps per operation |
| 1000 | About 1000 steps per operation |
Pattern observation: The work grows directly with the string length; double the length, double the work.
Final Time Complexity
Time Complexity: O(n)
This means the time to run these string operations grows in a straight line with the string size.
Common Mistake
[X] Wrong: "String functions like strlen or strcpy run in constant time because they just look at the string once."
[OK] Correct: These functions actually check each character until they find the end, so their time depends on string length.
Interview Connect
Understanding how string operations scale helps you write efficient code and answer questions about performance clearly.
Self-Check
"What if we used a function that only checked the first 5 characters of a string? How would the time complexity change?"