String searching (contains, strfind) in MATLAB - Time & Space Complexity

Time Complexity: String searching (contains, strfind)

O(n*m)

Understanding Time Complexity

We want to understand how the time it takes to search for a smaller string inside a bigger string changes as the strings get longer.

How does the search time grow when the input strings grow?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

text = 'hello world, welcome to matlab';
pattern = 'come';
index = strfind(text, pattern);
found = contains(text, pattern);

This code looks for the smaller string pattern inside the bigger string text using two functions: strfind and contains.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking each position in the big string to see if the smaller string starts there.
• How many times: For each character in the big string, it compares up to the length of the smaller string.

How Execution Grows With Input

As the big string gets longer, the number of checks grows roughly by the length of the big string times the length of the smaller string.

Input Size (n)	Approx. Operations
10	About 10 times length of pattern
100	About 100 times length of pattern
1000	About 1000 times length of pattern

Pattern observation: The work grows roughly in a straight line with the big string size, multiplied by the smaller string size.

Final Time Complexity

Time Complexity: O(n*m)

This means the time to search grows proportionally to the length of the big string times the length of the smaller string.

Common Mistake

[X] Wrong: "Searching for a string inside another always takes the same time no matter how long the strings are."

[OK] Correct: The search checks many positions and compares characters, so longer strings mean more work and more time.

Interview Connect

Understanding how string search time grows helps you explain and reason about code efficiency clearly, a useful skill in many programming tasks.

Self-Check

"What if the smaller string is always just one character? How would the time complexity change?"