7
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ Because the list is constant size the time complexity of the python min() or max() calls are O(1) - there is no "n". Caveat: if the values are strings, comparing long strings has a worst case O(n) running time, where n is the length of the strings you are comparing, so there's potentially a hidden "n" here. If you are calling the function in a loop, then the call is still O(1) but the contribution to time complexity of the loop is O(n), where n is the number of iterations of the loop. Of course if the loop contains dominant elements the complexity of the loop will be higher. (eg sort) $\endgroup$ Mar 12 at 11:37
  • 8
    $\begingroup$ We don't generally talk about the complexity of an algorithm with a specific input. Complexity describes its behavior over the spectrum of possible inputs. $\endgroup$
    – Barmar
    Mar 12 at 14:59

12 Answers 12

24
$\begingroup$

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.

$\endgroup$
9
  • 13
    $\begingroup$ @StephenBoesch The list is specified to have a constant size, so N is constant, so it's O(1) with the constant factor depending on N. $\endgroup$
    – kviiri
    Mar 12 at 7:55
  • 16
    $\begingroup$ @StephenBosch The list size is defined by the querent to be constant. Therefore the complexity is constant (and this demonstrates why time complexity is a poor tool for discussing a single instance). $\endgroup$
    – kviiri
    Mar 12 at 8:18
  • 2
    $\begingroup$ @StephenBoesch: Imagine the list is eg. a lookup table, which is always the same size no matter what the size our input is (the "input" here is some other thing our algorithm is acting on). Then finding the min() of this table as one step of our algorithm would be O(1), even if the table is huge. $\endgroup$ Mar 12 at 11:06
  • 4
    $\begingroup$ @user253751 That doesn’t make sense for asymptotic complexity analysis, since, as I said, that analysis is concerned with changes in runtime as the size of the input changes. $\endgroup$ Mar 12 at 23:36
  • 2
    $\begingroup$ Finding the best move in any given chess position is O(1), with an astronomically high constant. $\endgroup$
    – gnasher729
    Mar 13 at 22:27
13
$\begingroup$

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.

$\endgroup$
1
  • 4
    $\begingroup$ Depends what "constant sized list" means: It may mean: A list with a given number of elements but the elements may have different sizes. Example: A list of strings which can have one character or 10.000 characters. The "size of the input" of the list of 100 elements, each of one character length, differs from the list of 100 elements, each of 10.000 characters length. $\endgroup$ Mar 12 at 9:58
5
$\begingroup$

Sure, you could call it O(1) if you want.

So what if you choose to describe it that way? It's still going to iterate over the whole list, so describing it one way or the other doesn't change the real-world Python run time.

It's still something you want to avoid doing repeatedly for the same list, especially if the list isn't tiny. (Especially in a loop that can run many iterations.)

Being O(1) isn't the same thing as cheap, especially if you're "cheating" by taking large but fixed sizes as "constants" instead of part of your complexity calculation.

If anything, you've created an example of why complexity-class analysis is not the same thing as performance estimation, especially for a given finite range of problem sizes. If it feels "wrong" to call it O(1), this is why.

$\endgroup$
4
$\begingroup$

Yes

In general, if the time complexity of an algorithm is O(f(X)) where X is a characteristic of the input (such as list size), then if that characteristic is bounded by a constant C, the time complexity will be O(f(C)) = O(1).

This is especially useful with certain algorithms that have time complexities that look like e.g. O(N ^ K). This is superexponential, which isn't great, but if you can fix K to be bounded by a small constant, your runtime is polynomial, which is much better! (The downside is that your algorithm will have to refuse certain inputs, but hey those were going to take forever anyway.)


This here is the big limitation of complexity analysis: it can only tell you how fast certain functions grow, it will not tell you the absolute time taken. An algorithm that will always take a million years no matter the input is still O(1), after all.

To figure out the specific numbers, and if you'll need to cache the results from min and max, you'll need to measure the actual time your code takes, and decide if it is fast enough for your use case.

$\endgroup$
2
$\begingroup$

If the size of the lists as input to the min() and max() functions always are the same constant $k$, then you can find an upper bound (and lower bound) on the number of operations required to compute min() and max() that depends only on the constant size $k$ (plus some other constants), which results in a running time of $O(1)$.

Therefore, if the size of the lists always are the same, then the asymptotic time complexity will be $O(1)$. However, do keep in mind that the actual running time still depends on the size of the lists.

$\endgroup$
2
$\begingroup$

Usually, $\operatorname{O}\left(1\right) .$

Yeah, usually it'll be $\operatorname{O}\left(1\right) ,$ under normal assumptions.

A major exception would be if the list-elements could grow in complexity with input-size. For example, if the list-elements were themselves lists that grew with the input, then even a single comparison between two of the elements could be more than $\operatorname{O}\left(1\right) .$

But if the list-elements are, say, machine-primitives that have constant-time behavior, then, yeah, typically $\operatorname{O}\left(1\right) .$

$\endgroup$
2
$\begingroup$

Yes, any bounded amount of work is O(1).

Every algorithm applied to an input of bounded size takes O(1) time, however, and that is independent of any variables whatsoever, so there is never any reason to mention this as an attribute of any particular algorithm.

In the analysis of algorithms, though, you will often see O(1) used to refer to any bounded amount of work. The recurrence relation for the time taken by binary search, for example, is T(n) = T(n/2) + O(1).

$\endgroup$
2
$\begingroup$

Colloquially we refer to algorithms as $O(1)$ or $O(n\ \log n)$ or such. When you start talking about the Big-O complexity class of an operation over a constant sized object, it becomes important to use it more precisely. Us CS people get too lazy!

Big-O notation is applied to mathematical functions not computer algorithms. It explores the bounds on an operation as the independent variables in that function head off towards infinity. We cannot apply it to an algorithm without using extra words. For example, we might define a function $f(n)$ to be "the maximum number of comparisons needed to sort a list of length $n$." This describes a mathematical function, and thus we can plot it, and we can look at its behavior using Big-O complexity analyses.

So in this case, you have an algorithm "determine the maximum value in a list of a given size." But you still need to define your function on that algorithm. I can't say "determine the maximum number of values a list of some pre-specified size as the size of that list grows to infinity" any more than I can say "two plus two equals five for very large values of two."

I could pick some arbitrary unimportant variable, and say $f(n)$ is "the number operations does it take to find the maximum of a fixed-size length given that the price of tea in India is $n$". That would be a valid function we could apply Big-O notation to, and we would find that your algorithm's run time is $O(1)$ with respect to the price of tea in India. But we need something as an independent variable that can take on values that approach infinity.

To use Big-O meaningfully, you need to identify some function of a variable (or variables) which can approach infinity. Only then is a Big-O analysis meaningful.

$\endgroup$
-1
$\begingroup$

My understanding of the notion of time complexity is that it describes the change in the amount of time that an operation takes as the size of a single input to the function changes. The quote that @JoshRumbut gives says pretty much the same thing.

If, as in the case here, one is not talking about how the execution time of an operation changes as the input size changes, then the notion of time complexity does not apply. The time complexity for min() or max() operations run only on a list of a particular size is not O(?) anything The concept simply doesn't apply here.

What does make sense is to talk about the time complexity of min() and max() as the size of the input list changes. Since the execution time varies linearly with the size of the input list (either a linked list or an array), the time complexity of min() or max() on a simple list is 𝑂(N).

$\endgroup$
2
  • 1
    $\begingroup$ First, you don't have to guess or to interpret the meaning in any way yourself as there are precise definitions (have a look on Wikipedia for instance). Second, surely the concept can be applied. In fact, the notion has absolutely nothing to do with algorithm analysis per se, but you might as well apply it to a function that measures the number of apples in my garden as a function of the days passed since the start of the year or whatever. $\endgroup$
    – Juho
    Mar 13 at 7:27
  • $\begingroup$ The "precise definitions" vary. Also, the subject does say TIME complexity., but I don't disagree that the notion can apply to any CHANGING quantity. "number of apples in my garden as a function of the days passed since the start of the year". Exactly! In that case you are talk about a changing value, "the days passed since the start of the year". Here, we are talking about "apples in my garden on May 24". The notion of complexity doesn't apply to this single situation either. If there is no changing quantity, there is no notion of complexity. $\endgroup$
    – CryptoFool
    Mar 13 at 15:08
-1
$\begingroup$

Not really. With a constant size, such as 1,000,000, the time complexity of the min() and max() aren't O(1).

Consider a nested list whose every element is an m sized list, which then elments are:

[0] * n + [k]

where k is a number. The time complexity of comparating two elements is O(m), so the complexity of min() and max() is O(m).

$\endgroup$
4
  • $\begingroup$ In your example the complexity is O(m), but m is a constant, namely 1,000,000 so it is O(1000000) ~ O(1). $\endgroup$ Mar 12 at 11:41
  • $\begingroup$ @RichFarmbrough No, m is not constant here, since it refers to the lengths of the elements $\endgroup$
    – univalence
    Mar 12 at 13:10
  • $\begingroup$ This answer sounds like it might be correctly referring to a case in which the operation wouldn't be O(1), though it's somewhat difficult to be sure. A more clear description might be more helpful. $\endgroup$
    – Nat
    Mar 13 at 22:09
  • $\begingroup$ I don't understand why you've made this complicated with elements [0]*n+[k]. The elements of the nested list don't seem to matter much; you could have just said they are all 42 and your reasoning would work just as well. $\endgroup$
    – D.W.
    Mar 14 at 18:47
-2
$\begingroup$

The time complexity of the algorithm is still O(N)

Sure, in a sense the max and min of a constant list is a constant, but no general implementation can know these values without running first.

The time complexity of the call to the min and max function MAYBE O(1)

A compiler can recognize that the result of the call is a compile-time constant if the argument is a constant, then precompute these values and place the result directly in the machine code. I doubt that the python interpreter can do this optimization, but I do not know for sure whether it might perform some just-in-time compilation tricks or cache the results. In the end, it is out of your hand.

EDIT: I was assuming that constant sized implies that OP does not change the values of the entries at any point. I might need to rephrase this. However, this is my point: If the list ist just constant in size, but not constant in value, I'm allowed to change the last N-1 entry to a value larger than the previous max value. So then the result of max() must change. How can a general algorithm work this out without touching all elements up to the last one?

If the question is intended to infer the complexity of an algorithm that has M values as input, and is using max and min, then it depends on whether size N is dependent on M. That is not given in the question, thus no conclusive answer can be given.

$\endgroup$
6
  • $\begingroup$ The list is constant size not a list of constants. $\endgroup$ Mar 12 at 11:38
  • $\begingroup$ @RichFarmbrough Relevant point, my answer took it differently. But to me, this is the argument. If the list ist just constant in size, but not constant in value, I'm allowed to change the last N-1 entry to a value larger than the previous max value. So then the result of max() must change. How can a general algorithm work this out without touching all elements up to the last one? $\endgroup$ Mar 12 at 11:43
  • $\begingroup$ Yes, you need to recalculate (though if we know just one given item has been changed we can do this very fast). The point is that there is an upper limit to calculating max(x1, .... xc) where c is a constant. It may be large, but that's fine from a theoretical point of view. See my comment to the original question for a little more. $\endgroup$ Mar 12 at 11:56
  • $\begingroup$ If N is constant, then O(N) = O(C) = O(1). $\endgroup$
    – Jasmijn
    Mar 12 at 13:26
  • $\begingroup$ How can a general algorithm [for max()] work this out without touching all elements up to the last one? This may be trivial depending on domain: you can tell the max of any collection of numbers $\overline m \ with -\overline m \in ℕ$ is -1 when you encounter the first -1. Or the max among unsigned 8 bit numbers finding $2^8-1$. $\endgroup$
    – greybeard
    Mar 13 at 6:56
-3
$\begingroup$

It depends if Array/List is sorted or not. The given answer is incorrect and my one was downvoted. Thanks voting bots!

https://stackoverflow.com/questions/35386546/big-o-of-min-and-max-in-python

FROM WIKIPEDIA:

O(1) is applicable

An algorithm is said to be constant time O(1)... In a similar manner, finding the minimal value in an array sorted in ascending order

O(n) is applicable

O(n).. finding the minimal value in an unordered array is not a constant time operation as scanning over each element in the array is needed in order to determine the minimal value

You need to check all of the the values to find the minimal one if the list is not sorted. My first idea is that Python does not have a hidden support for caching function return values. I'm not certain if min(value) is considered deterministic in python if you supply a reference instead of an actual list.

Below is an easy way to memoize a function and its return values in Python. If you apply this the complexity of your function can be reduced to O(1)+n

def memoize(func):
cache = dict()

def memoized_func(*args):
    if args in cache:
        return cache[args]
    result = func(*args)
    cache[args] = result
    return result

return memoized_func
$\endgroup$
5
  • $\begingroup$ Python's Higher-order functions module provides @functools.cache(user_function). Still, this just shifts effort from determining argument order to determining argument equivalence. $\endgroup$
    – greybeard
    Mar 13 at 6:37
  • $\begingroup$ Look at the radix search proof and you will see that your argument is wrong. $\endgroup$
    – kelalaka
    Mar 13 at 19:43
  • $\begingroup$ @kelalaka please point me towards the radix search proof too show that you're right then. Seems people here read an article on wikipedia without even grasping the concept of time complexity. O(1) is applicable if the array is sorted. From wikipedia " In a similar manner, finding the minimal value in an array sorted in ascending order". The original question never said if the array was sorted or not. The joys of the online world. $\endgroup$ Mar 14 at 8:10
  • $\begingroup$ Radix sort is O(nw) by the way $\endgroup$ Mar 14 at 8:22
  • $\begingroup$ To expand on what @greybeard said, a memoized function that takes a list will have the added complexity of looking up the list in the cache. And iirc a good hash function for lists will take time proportionate to the size of the list. You can, I suppose, amortize the work for calculating the hash by redoing it whenever you insert an element, but if you were to go to that length, then you might as well do the same with calculating the max/min. $\endgroup$
    – cole
    Mar 14 at 19:32

Not the answer you're looking for? Browse other questions tagged or ask your own question.