String search functions (strpos, strstr) in PHP - Time & Space Complexity

Time Complexity: String search functions (strpos, strstr)

O(n*m)

Understanding Time Complexity

When we use string search functions like strpos or strstr, we want to know how long they take as the string gets bigger.

We ask: How does the time to find a substring grow when the string length grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

$string = "Hello, this is a simple example string.";
$search = "simple";
$pos = strpos($string, $search);
if ($pos !== false) {
    echo "Found at position: $pos";
} else {
    echo "Not found.";
}
    

This code looks for the position of a smaller string inside a bigger string.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each character in the main string to see if the search string starts there.
• How many times: Up to once for each character in the main string until the substring is found or the string ends.

How Execution Grows With Input

As the main string gets longer, the function may check more characters to find the substring.

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

Pattern observation: The number of checks grows roughly in direct proportion to the string length.

Final Time Complexity

Time Complexity: O(n*m)

This means the time to find the substring grows roughly in proportion to the product of the length of the main string (n) and the length of the substring (m).

Common Mistake

[X] Wrong: "String search is always instant, no matter how long the string is."

[OK] Correct: The function may need to check many characters one by one, so longer strings usually take more time.

Interview Connect

Understanding how string search time grows helps you explain efficiency clearly and shows you know how basic functions behave with bigger data.

Self-Check

"What if we searched for multiple different substrings one after another? How would the time complexity change?"