String as character array in Data Structures Theory - Time & Space Complexity

Time Complexity: String as character array

O(n)

Understanding Time Complexity

When we treat a string as a list of characters, it helps to understand how operations on it grow as the string gets longer.

We want to know how the time needed changes when we do things like reading or searching characters in the string.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function findChar(str, target) {
  for (let i = 0; i < str.length; i++) {
    if (str[i] === target) {
      return i;
    }
  }
  return -1;
}

This code searches for a character in a string treated as an array of characters and returns its position or -1 if not found.

Identify Repeating Operations

• Primary operation: Looping through each character in the string one by one.
• How many times: Up to the length of the string, stopping early if the character is found.

How Execution Grows With Input

As the string gets longer, the number of characters checked grows roughly the same as the string length.

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

Pattern observation: The work grows directly with the string length; doubling the string roughly doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to find a character grows linearly with the string length.

Common Mistake

[X] Wrong: "Searching a character in a string is always instant or constant time."

[OK] Correct: Because the search may need to check many characters one by one, the time depends on the string length.

Interview Connect

Understanding how string operations scale helps you explain your code choices clearly and shows you know what happens behind the scenes.

Self-Check

"What if the string was stored as a linked list of characters instead of an array? How would the time complexity change?"