This is not my area but it never hurts to examine things and see what we spot. The first and last are both linear with a constant of 2 (for the two iterations) so O(2N). The second one looks to have a constant of 4 given there are four iterations, but still linear.
The third one would be the least efficient owing that it is quadratic (nested iteration). It could be cured by caching the max() before the loop. It never changes. Then it would be linear with a constant of 2.
Owing that we could very likely conclude that the source code for max()
is highly optimized. The fourth one would be a best bet and itâs doubtful we as learners or even seasoned programmers will ever top that for this language. I suspect the source code is written in some flavor or C.
The thing I like about the first example is it is closest to a naive implementation It still uses built-ins, though. list()
and dict.items()
. The fully naive form will use only linear iteration.
>>> def max_key(d):
k, v = (None, float("-inf"))
for h in d:
if d[h] > v:
k, v = (h, d[h])
return k
>>> max_key({"a":100, "b":10, "c":1000})
'c'
>>>
The only difference is that it uses negative infinity as the minimum instead of a value from the dictionary.