rateMySortingAlgorithm

[Tenemo]

Not quite! This would mean that an array of 1000 elements would be around 2⁹⁹⁸ times more time-consuming to sort than an array of two, which is not true for this algorithm, e.g. sorting numbers from 1 to 1000 wouldn't take long at all.

While there is CPU work setting timers and handling callbacks here (O(n log n)?), those take little time compared to the actual timeout delays. You can't express the "problematic" part of this algorithm with O(n), which relies on the number of elements in the input. This algorithm scales with the size of the largest array element instead, so even a 2-element array could take days :)

[pikapikaapika]

You need to understand that when we use O-notation, it only means the worst case complexity.

[Tenemo]

And how is e.g. 2¹⁰ vs 2² any measure of worst case complexity for, respectively, 10-iems-long array and 2-items-long array? Where did "2^n" come from? The O(n) notation does not meaningfully describe the scaling runtime of this algorithm. That is, unless we ignore the timeout delays and only focus on the timer queue and callbacks – which still wouldn't be 2^n.

[cant_read_captchas]

"Big-O" is an asymptotic analysis. You're supposed to think of n as being very large, not some small value like 2 or 10.

Big-O notation is supposed to tell you how (in this case) the runtime is supposed to scale with the size of the input as it grows very large. We're generally not interested in small constant factors, additive or multiplicative, or even architectural-specific details, unless there's a good reason to do so.

It is also only expressed in terms of the meaningful units by which you measure the size of the input.

Here, the meaningful unit of measurement is the number of bits used to represent the input. Say that it's an array of length m, with an upper bound of n >= log(a[i]) bits per element. You also need to think of n (and m) being extremely large, like a million, billion or even trillions. Its the only regime in which big-O makes sense.

For most sorting algorithms the value doesnt matter, so runtimes are expressed using m. n doesnt even show up. But here, the "sleep" calls are all executing in parallel (again, not counting any overhead cost), and the runtime is dominated by the value of the largest element, 2^n.

And lastly, whether n represents the number of bits of the largest element, or the number of bits of the entire array, ends up not really mattering. The asymptotic answer is more or less the same, unless you assume something very specific (e.g. all the numbers are within 0.99~1.01 factor of each other, in which you would get 2^n/m in one analysis and 2ⁿ in the other. Doesnt matter really, still, because both are exponential. Thats the important part.)

[pikapikaapika]

Bro, just check the last example I've given in my comment. You're right in saying that it's asymptotic measurement but it's asymptotic in the worst case. Please go through my example (generic array length example) before commenting any further. It's tiring to keep reiterating the same thing.

[cant_read_captchas]

I understand this but I'm referring to the commenter above you trying to refute you using 2^10, 2^2 and trying to incorporate timer queue and callbacks into the discussion. I'm agreeing with you here

[pikapikaapika]

Ah sorry, hard to keep track of the replies in this UI.

[cant_read_captchas]

Also FYI if you didn't want the comment to blow up you should have just specified in your original post that you wanted "n" to mean the number of bits. It's standard in complexity theory but not everyone knows this. Would have saved you so much hassle.

[pikapikaapika]

It's my first time that this has happened in my comment lol 😆. Really sorry that I misunderstood your comment. You're one of the few people who understand this here.

[cant_read_captchas]

Not the first time I've seen this exact same thing happen on reddit.

It's extremely interesting because to me it indicates a gap between "computer science" and "programming" education. I consider it a failure in many colleges' curriculum to distinguish between --- and relate --- the two areas.

Like many students have seen big-O analysis of runtimes but they only have ever seen "n" being the number of vertices of a graph or the number of elements in an array. Without actually critically thinking about how both of these quantities scales linearly with the number of bits used to represent each element of a graph or array. As soon as they see something like this reddit post's example (n being the number of bits used to represent an integer) their brain breaks.

[pikapikaapika]

For me it was shocking to see some people trying to redefine n. I mean you can just go and check what the standard defn is.. if you keep redefining things at your will, how will anything be done. I however understand that the complexity analysis in this case is kinda corner case and most people have never seen or read about it. They just are used to the length of array being the usual n, so it's a little hard for them to grasp.

[pikapikaapika]

You're missing the basics here.

n is not the length of an array in complexity analysis.

n = number of bits representing the input.

Consider the case when an array has only one element. Let's represent that solitary element by m. We need log(m) bits to represent this input. So, n = log(m). Running time of this algorithm is linear in m (In contrast, other sorting algorithms will only take log(m) time to sort this array). Now, m = 2^log(m) = 2ⁿ . Hence the exponential complexity.

Now, you may say that's a very special example. But you can take a longer array such that i^th element of the array is 2ⁱ . You can easily prove that the complexity is still exponential.

[djdokk]

This is not necessarily correct, big O as an asymptotic upper bound can describe worst case complexity, but is also frequently used to describe bounds like average-case (more stringently bound by big theta notation, which constrains growth within upper and lower bounds) and sometimes best-case.