What are the Big-O Time Complexities of Common PHP Array Functions?

Big-O for PHP Functions

When working with PHP, the efficiency of various built-in functions can vary significantly. This article aims to provide insights into their theoretical (or practical) big-O times.

Lookups

• array_key_exists: O(n), but effectively close to O(1) due to hash lookups.
• isset($array[$index]): O(n), also close to O(1) due to hash lookups.
• in_array: O(n), slower than hash-based lookups.
• array_search: O(n), similar to in_array.

Queue Functions

• array_push: O(∑ var_i, for all i)
• array_pop: O(1)
• array_shift: O(n), re-indexes keys.
• array_unshift: O(n ∑ var_i, for all i), slower due to re-indexing.

Array Intersection, Union, Subtraction

• array_intersect_key: O(Max(param_i_size)*∑param_i_count, for all i) if intersection is 100%.
• array_intersect: O(n^2*∑param_i_count, for all i) if intersection is 100%.
• array_intersect_assoc: Similar to array_intersect_key.
• array_diff: O(π param_i_size, for all i), product of all param sizes.
• array_diff_key: O(∑ param_i_size, for i != 1).

Random

• shuffle: O(n)
• array_rand: O(n)

Obvious Big-O

• array_fill: O(n)
• array_fill_keys: O(n)
• range: O(n)
• array_splice: O(offset length)
• array_slice: O(offset length) or O(n) if length is NULL
• array_keys: O(n)
• array_values: O(n)
• array_reverse: O(n)

Note

1. All calculations assume hash lookups are O(1).
2. Asymptotic performance may vary depending on specific implementation details and the input data.
3. Arrays are zero-based, so array_push pushes to the end of the array.

The above is the detailed content of What are the Big-O Time Complexities of Common PHP Array Functions?. For more information, please follow other related articles on the PHP Chinese website!