Array reduce function in PHP - Time & Space Complexity

Time Complexity: Array reduce function

O(n)

Understanding Time Complexity

When using the array reduce function, it's important to know how the time it takes grows as the array gets bigger.

We want to find out how many steps the reduce function needs when working on arrays of different sizes.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

$array = [1, 2, 3, 4, 5];
$result = array_reduce($array, function($carry, $item) {
    return $carry + $item;
}, 0);
    

This code sums all numbers in the array using array_reduce.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The callback function runs once for each item in the array.
• How many times: Exactly as many times as there are elements in the array.

How Execution Grows With Input

As the array gets bigger, the number of times the callback runs grows directly with the number of items.

Input Size (n)	Approx. Operations
10	10 callback calls
100	100 callback calls
1000	1000 callback calls

Pattern observation: The work grows evenly as the array size grows.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows in a straight line with the number of items in the array.

Common Mistake

[X] Wrong: "array_reduce runs faster than looping because it's a built-in function."

[OK] Correct: The reduce function still processes each item one by one, so it takes time proportional to the array size, just like a loop.

Interview Connect

Understanding how array_reduce works helps you explain how built-in functions handle data and why their speed depends on input size, a useful skill in coding interviews.

Self-Check

"What if the callback function inside array_reduce called another loop over the array? How would the time complexity change?"