String length and counting in PHP - Time & Space Complexity

Time Complexity: String length and counting

O(n)

Understanding Time Complexity

We want to understand how the time to count characters in a string grows as the string gets longer.

How does the program's work increase when the string size increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

$string = "hello world";
$count = 0;
for ($i = 0; $i < strlen($string); $i++) {
    if ($string[$i] === 'l') {
        $count++;
    }
}
echo $count;
    

This code counts how many times the letter 'l' appears in the string.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each character of the string.
• How many times: Once for every character in the string.

How Execution Grows With Input

As the string gets longer, the program checks each character one by one.

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

Pattern observation: The work grows directly with the string length.

Final Time Complexity

Time Complexity: O(n)

This means the time to count characters grows in a straight line as the string gets longer.

Common Mistake

[X] Wrong: "Counting characters takes the same time no matter the string length."

[OK] Correct: The program must look at each character, so longer strings take more time.

Interview Connect

Understanding how counting characters scales helps you explain how programs handle text efficiently.

Self-Check

"What if we used a function that counts characters without looping explicitly? How would the time complexity change?"