Common validation patterns in PHP - Time & Space Complexity

Time Complexity: Common validation patterns

O(n)

Understanding Time Complexity

When checking data for correctness, we often run validation steps. Understanding how long these checks take helps us write faster programs.

We want to know how the time to validate grows as the data size grows.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function validateEmails(array $emails) {
    foreach ($emails as $email) {
        if (!filter_var($email, FILTER_VALIDATE_EMAIL)) {
            return false;
        }
    }
    return true;
}
    

This code checks if every email in a list is valid, stopping early if any email is invalid.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each email to validate it.
• How many times: Up to once per email, stopping early if invalid.

How Execution Grows With Input

As the number of emails grows, the checks grow roughly the same amount, unless an invalid email appears early.

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

Pattern observation: The work grows linearly with the number of emails.

Final Time Complexity

Time Complexity: O(n)

This means the time to validate grows directly with the number of emails.

Common Mistake

[X] Wrong: "Validation always takes the same time no matter how many inputs there are."

[OK] Correct: Each input needs checking, so more inputs usually mean more work.

Interview Connect

Understanding how validation time grows helps you write efficient checks and explain your code clearly in interviews.

Self-Check

"What if we changed the validation to check only the first 5 emails regardless of list size? How would the time complexity change?"