Time Complexity: Substring extraction
O(k)
0
0
Substring extraction in PHP - Time & Space Complexity
Understanding Time Complexity
When we extract a part of a string, it is important to know how the time needed grows as the string gets longer.
We want to find out how the work changes when the input string size changes.
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
$string = "Hello, world!";
$start = 7;
$length = 5;
$substring = substr($string, $start, $length);
echo $substring;
This code takes a string and extracts a smaller part starting at a certain position with a given length.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: Copying characters from the original string to create the substring.
- How many times: The number of characters copied equals the length of the substring requested.
How Execution Grows With Input
As the substring length grows, the work grows proportionally because each character must be copied.
| Input Size (substring length) | Approx. Operations |
|---|---|
| 10 | About 10 character copies |
| 100 | About 100 character copies |
| 1000 | About 1000 character copies |
Pattern observation: The time grows linearly with the length of the substring extracted.
Final Time Complexity
Time Complexity: O(k)
This means the time needed grows directly with the length of the substring you want to extract.
Common Mistake
[X] Wrong: "Extracting a substring always takes the same time no matter how long it is."
[OK] Correct: Actually, the function must copy each character one by one, so longer substrings take more time.
Interview Connect
Understanding how substring extraction scales helps you reason about string operations in real projects and interviews.
Self-Check
"What if we extract a substring without specifying length, how would the time complexity change?"