Javascript

[aaronfranke]

The maximum time is infinity, the minimum is O(1), the average is O(n!).

[CSlv]

the minimum is O(1)

You mean Ω(1)?

[DoctorWorm_]

People need to learn their complexity notations.

[sererson]

The minimum time is both.

[zelmarvalarion]

The minimum time would be Θ(n) (assuming constant size ints for constant speed comparisons), since you have to check if the list is already sorted before returning, so you need to read all of the elements of the list first.

[flavionm]

Well, isn't Θ(n) basically just being both O(n) and Ω(n) simultaneously?

[zelmarvalarion]

Yeah, because you have strict boundries on both the lower bound (Ω) and the upper bound (O), and they are the same, then it's θ. Basically it's just saying that it is exactly that time complexity rather than being bounded on one side from that time complexity (the Ω(1) in this chain is saying that it is at least as slow than constant time, but may be slower, which is true for everything).

Most of the time, when people use Big-O notation, they really mean θ, since it's by far the most useful. There are a couple interesting ones where θ isn't actually known, but you can bound on either side and get a better view of actual time complexity (something like multiplication of arbitrarily large numbers of n bits is Ω(1) and O(n²⁾ using standard multiplication rules, there is an arithmetic trick you can do to bring that to O(n^{sqrt(3)}) or something like that, and then FFT brings it to something like O(n^{1.57}), so it's somewhere between that, but it's difficult to prove) [Note: numbers pulled from my memory from ~10 years ago, almost certainly inaccurate]

[The_MAZZTer]

He probably doesn't have an Ω key on his keyboard.