Array map function in PHP - Time & Space Complexity

Time Complexity: Array map function

O(n)

Understanding Time Complexity

We want to understand how the time needed to run an array map function changes as the array gets bigger.

Specifically, how does the work grow when we apply a function to each item in an array?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

$array = [1, 2, 3, 4, 5];
$result = array_map(function($item) {
    return $item * 2;
}, $array);

This code takes each number in the array and doubles it, creating a new array with the results.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Applying the function to each element in the array.
• How many times: Once for every element in the array.

How Execution Grows With Input

As the array gets bigger, the number of times we apply the function grows directly with the number of items.

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

Pattern observation: The work grows in a straight line with the size of the array.

Final Time Complexity

Time Complexity: O(n)

This means the time to finish grows directly with the number of items in the array.

Common Mistake

[X] Wrong: "The array_map function runs in constant time no matter the array size."

[OK] Correct: The function must visit each item to apply the callback, so time grows with array size.

Interview Connect

Knowing how array_map scales helps you explain how your code handles bigger data, a skill interviewers appreciate.

Self-Check

"What if the callback function inside array_map itself contains a loop? How would the time complexity change?"