Time Complexity: Searching and replacing text
O(n)
0
0
Searching and replacing text in Python - Time & Space Complexity
Understanding Time Complexity
When we search and replace text in a string, we want to know how the time it takes changes as the text gets longer.
We ask: How does the work grow when the input text grows?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
text = "hello world hello"
old = "hello"
new = "hi"
result = text.replace(old, new)
print(result)
This code replaces all occurrences of "hello" with "hi" in the given text string.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Checking each part of the text to find matches of the old word.
- How many times: The operation runs once for each character in the text string.
How Execution Grows With Input
As the text gets longer, the program checks more characters to find matches.
| 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 text.
Final Time Complexity
Time Complexity: O(n)
This means the time to replace text grows in a straight line as the text gets longer.
Common Mistake
[X] Wrong: "Replacing text takes the same time no matter how long the text is."
[OK] Correct: The program must look through the whole text to find what to replace, so longer text means more work.
Interview Connect
Understanding how searching and replacing text scales helps you explain how programs handle big inputs smoothly.
Self-Check
"What if we replaced only the first occurrence instead of all? How would the time complexity change?"