String searching and extraction in C Sharp (C#) - Time & Space Complexity

Time Complexity: String searching and extraction

O(n * m)

Understanding Time Complexity

When we search or extract parts of a string, the time it takes depends on the string's length.

We want to know how the work grows as the string gets longer.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

string text = "Hello, welcome to the world of C# programming.";
string wordToFind = "world";

int index = text.IndexOf(wordToFind);
if (index != -1)
{
    string extracted = text.Substring(index, wordToFind.Length);
    Console.WriteLine(extracted);
}

This code searches for a word inside a string and extracts it if found.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The search method IndexOf scans the string to find the word.
• How many times: It checks characters one by one until it finds the word or reaches the end.

How Execution Grows With Input

As the string gets longer, the search checks more characters.

Input Size (n)	Approx. Operations
10	About 10 character checks
100	About 100 character checks
1000	About 1000 character checks

Pattern observation: The work grows roughly in direct proportion to the string length.

Final Time Complexity

Time Complexity: O(n * m)

This means the time to search grows linearly with the string length and the word length.

Common Mistake

[X] Wrong: "Searching a string is always instant, no matter how long it is."

[OK] Correct: The program must check characters one by one, so longer strings take more time.

Interview Connect

Understanding how string search time grows helps you explain efficiency clearly and shows you know how programs handle text.

Self-Check

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