Array search functions in PHP - Time & Space Complexity

Time Complexity: Array search functions

O(n)

Understanding Time Complexity

When we search for a value in an array, the time it takes depends on how many items are in the array.

We want to understand how the search time grows as the array gets bigger.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function searchArray(array $arr, $target) {
    foreach ($arr as $item) {
        if ($item === $target) {
            return true;
        }
    }
    return false;
}

This code looks through each item in the array to find if the target value exists.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Looping through each element in the array.
• How many times: Up to once for each item until the target is found or the array ends.

How Execution Grows With Input

As the array gets bigger, the search might check more items.

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

Pattern observation: The number of checks grows roughly the same as the number of items.

Final Time Complexity

Time Complexity: O(n)

This means the time to search grows linearly with the size of the array.

Common Mistake

[X] Wrong: "Searching an array always takes the same time no matter how big it is."

[OK] Correct: The search might have to check many items, so bigger arrays usually take longer.

Interview Connect

Understanding how search time grows helps you explain and improve code that works with lists.

Self-Check

"What if the array was sorted and we used a binary search instead? How would the time complexity change?"