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

Big-O Time Complexities for PHP Functions

This article presents a compilation of theoretical and practical Big-O time complexities for some of the most commonly used PHP built-in functions.

Lookup Functions

• isset( $array[$index] ) and array_key_exists: Despite being classified as O(n), these functions perform near O(1) hash lookups.
• in_array: Performs a linear search through the array, resulting in an O(n) complexity.
• array_search: Similar to in_array, but returns the value, leading to an O(n) complexity.

Queue Functions

• array_push: O(∑ var_i)
• array_pop: O(1)
• array_shift: O(n)
• array_unshift: O(n ∑ var_i)

Array Intersection, Union, and Subtraction

• array_intersect_key: O(Max(param_i_size) * ∑param_i_count) for 100% intersection, or O(∑param_i_size) for 0% intersection.
• array_intersect: O(n^2 * ∑param_i_count) for 100% intersection, or O(n^2) for 0% intersection.
• array_intersect_assoc: Similar to array_intersect_key.
• array_diff: O(π param_i_size) for all parameters.
• array_diff_key: O(∑ param_i_size) for all parameters not equal to the first.
• array_merge: O(∑ array_i) for all parameters except the first.
• (union): O(n) for the second array.
• array_replace: O(∑ array_i) for all parameters.

Random Functions

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

Obvious Big-O Functions

• array_fill, array_fill_keys: O(n)
• range: O(n)
• array_splice, array_slice: O(offset length)
• array_keys, array_values: O(n)
• array_reverse: O(n)
• array_pad: O(pad_size)
• array_flip: O(n)
• array_sum, array_product: O(n)
• array_reduce: O(n)
• array_filter, array_map: O(n)
• array_chunk, array_combine: O(n)

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