Menu
What is the big O of the min and max functions in Python? Are they O(n) or does Python have a better way to find the minimum and maximum of an array? If they are O(n), isn't it better to use a for-loop to find the desired values or do they work the same as a for-loop?
409
The time complexity of max() function in python is O(n) .
The time complexity of comparating two elements is O(m), so the complexity of min() and max() is O(m).
Big-O notation signifies the relationship between the input to the algorithm and the steps required to execute the algorithm. It is denoted by a big "O" followed by an opening and closing parenthesis. Inside the parenthesis, the relationship between the input and the steps taken by the algorithm is presented using "n".
Hence, len() function in Python runs in O(1) complexity. Note: This might seem very beneficial, but remember that it puts a remarkable burden on the interpreter during the data definition phase. This is one of the many reasons why Python is slower during competitive programming, especially with big inputs.
It's O(n). It's a general algorithm, you can't find the max/min in the general case without checking all of them. Python doesn't even have a built-in sorted collection type that would make the check easy to specialize.
A for loop would have the same algorithmic complexity, but would run slower in the typical case, since min/max (on CPython anyway) are running an equivalent loop at the C layer, avoiding bytecode interpreter overhead, which the for loop would incur.
64
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
