HiveBrain v1.2.0
Get Started
← Back to all entries
patternpythonMajor

Time complexity of min() and max() on a list of constant size?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
constantsizetimeminmaxandlistcomplexity

Problem

If you use min() or max() on a constant sized list, even in a loop, is the time complexity O(1)?

Solution

That depends what exactly you mean by "constant sized". The time to find the minimum of a list with 917,340 elements is $O(1)$ with a very large constant factor. The time to find the minimum of various lists of different constant sizes is $O(n)$ and likely $\Theta(n)$ where $n$ 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.

Context

StackExchange Computer Science Q#136481, answer score: 28

Revisions (0)

No revisions yet.