Time Complexity: Array walk function
O(n)
0
0
Array walk function in PHP - Time & Space Complexity
Understanding Time Complexity
We want to understand how the time taken by the array walk function changes as the array gets bigger.
Specifically, we ask: How does the number of steps grow when the array size grows?
Scenario Under Consideration
Analyze the time complexity of the following code snippet.
$array = [1, 2, 3, 4, 5];
array_walk($array, function(&$value) {
$value *= 2;
});
print_r($array);
This code doubles each value in the array by walking through every element once.
Identify Repeating Operations
Identify the loops, recursion, array traversals that repeat.
- Primary operation: The function visits each element of the array once.
- How many times: Exactly once per element, so as many times as the array length.
How Execution Grows With Input
As the array gets bigger, the function takes longer because it must visit each new element.
| Input Size (n) | Approx. Operations |
|---|---|
| 10 | 10 visits |
| 100 | 100 visits |
| 1000 | 1000 visits |
Pattern observation: The number of steps grows directly with the number of elements.
Final Time Complexity
Time Complexity: O(n)
This means the time to complete grows in a straight line with the size of the array.
Common Mistake
[X] Wrong: "The array_walk function runs in constant time no matter the array size."
[OK] Correct: Because array_walk must visit each element to apply the function, the time depends on how many elements there are.
Interview Connect
Knowing how array functions scale helps you write efficient code and explain your choices clearly in interviews.
Self-Check
What if we replaced array_walk with a nested loop that calls array_walk inside another loop? How would the time complexity change?