In the first block of code the block of code runs the min function over the whole array, which takes O(n) time. Now considering it is in a loop of length n then the total time is O(n^2)
Looking at the 2nd block of code. Note that the min function is only comparing 2 values, which is arguably O(1). Now considering that it is in a loop of length n. The total time is simply the summation of O(n+n+n), which is equal to O(n)
Answer from March_G on Stack OverflowHi! I am having a hard time understanding if the builtin min function in python is of time complexity O(1). Since it might have to go through the list of elements, won't it be O(n) instead. I have seen another solution where they used 2 seperate stacks for maintaining stack and min_element. Is that a better way to do it to ensure that all methods are of O(1) time complexity? Any help is appreciated!
This is the problem I solved recently: 155. Min Stack (LC)
In the first block of code the block of code runs the min function over the whole array, which takes O(n) time. Now considering it is in a loop of length n then the total time is O(n^2)
Looking at the 2nd block of code. Note that the min function is only comparing 2 values, which is arguably O(1). Now considering that it is in a loop of length n. The total time is simply the summation of O(n+n+n), which is equal to O(n)
In the first code, it gives an array to the min() function, and this O(n) time complexity because it checks all elements in the array, in the second code, min() functions only compare two values and it takes O(1)
That depends what exactly you mean by "constant sized". The time to find the minimum of a list with 917,340 elements is 
with a very large constant factor. The time to find the minimum of various lists of different constant sizes is 
and likely 
where 
is the size of each list. Finding the minimum of a list of 917,340 elements takes much longer than finding the minimum of a list of 3 elements.
I found this quote from the Wikipedia article on time complexity helpful:
The time complexity is generally expressed as a function of the size of the input.
So if the size of the input doesn't vary, for example if every list is of 256 integers, the time complexity will also not vary and the time complexity is therefore O(1). This would be true of any algorithm, such as sorting, searching, etc.
I'm implementing an algorithm and I need a data structure with both very fast lookup of arbitrary elements like you get from a hash table and similar to a priority queue very fast lookup of the highest priority element ordered by a key associated with each item.
Is there anyway I can accomplish this? I thought of just using a set and something like min(set, lambda x: x.key), would this have to iterate through all elements?
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.
To find the maximum or minimum of a sequence, you must look at each element once, thus you can't get better than O(n).
Of course, Python min and max have O(n) too: docs.
You can write your own min/max function with a for loop and it will have the same complexity, but will be slower because it is not optimized in C.