patternpythonMajor
Time complexity of min() and max() on a list of constant size?
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.