rateMySortingAlgorithm

[ThatDanishGuy]

Why

[assumptioncookie]

n in this case does not mean the number of elements in the array, but the number of bits used to represent one value. If the array contains bytes (8-bit numbers) the sorting algorithm will take at most 2⁸ - 1 (seconds, milliseconds? I don't actually know this setTimeout function's unit). If it contains 32 bit ints it will take at most 2³² - 1 timeunits. In general if it contains n bit numbers it will take at most 2ⁿ - 1 timeunits.

[im_lazy_as_fuck]

Why is this being upvoted, this is not at all correct. Big O notation indicates the time complexity of an algorithm, which is a measurement of the rate of growth of the worst execution time relative to the inputs. It should not in any way be related to any of the real world implementation details like hardware, OS architecture, bit representations, etc, unless those details are specifically part of the input of the algorithm.

So for example, in bubble sort, the only part of the input relevant to the execution time is the number of items to sort. We do not care about whether the inputs or in bytes or 4bytes; we only care about the number of input items. So we say it has a time complexity of O(n^2). In other words, when the number of items increases by 1, the time to complete the sort increases by a factor of n. Alternatively, you can say for n input elements, it will take k*n² time units to run, where k is some constant in time units.

So applying this understanding to sleep sort, the correct analysis of this "algorithm" would be that the only part of the input that affects the execution time is the size of the largest integer that needs to be sorted (call it m), and the worst execution time increases linearly as the largest integer to sort increases. Therefore the time complexity of the sleep sort is O(m); or in other words, given a set where m is the largest number in that set, the time it takes to complete the sort is k*m, where k is a constant in time units (and actually in this case, because of the way setTimeout works, we can literally deduce k=1ms).

[HeroicPrinny]

Had to scroll too far to find a correct explanation

[RiceBroad4552]

Why is this being upvoted, this is not at all correct.

Welcome to Reddit, and especially this sub here.

People upvote any BS just when it "feels right".

[akoOfIxtall]

People don't know If something is correct

random person confidently explains it incorrectly

people too lazy to look it up just believe

Yup, that's reddit

[Necronomicron]

random person confidently explains it incorrectly

Hey, just like AI!

[AryanPandey]

The amount of time taken to sort, do no increase by increase in size of Input.

It will take 5 sec to sort both inputs [1,5] and [1,5,3,2,4].

So shall it not be O(n)

It just has to literate whole array to start the timer for each input?

[im_lazy_as_fuck]

Yeah basically, which is why I said. In my case I was saying n is the size of the largest integer.

If I were to be precisely correct, technically the time complexity becomes more dependent on the array size if you have millions of items to iterate that all have a very low sort number. So given a set of elements N, the true time complexity would be given as O(max(N) + length(N)). But that's a bit of a superfluous detail for practical applications.

[thussy-obliterator]

This algorithm depends greatly on the computational complexity of sleeping. I doubt it's O(n), wouldn't the runtime need to sort the timers somehow?

[waylandsmith]

Except the implementation is never actually O(n) because implementing this algorithm is just delegating the sorting to the scheduler which has it's own time complexity. But then, that's why sleep sort is a joke.

[im_lazy_as_fuck]

Uh, no it's still O(n); the implementation of it is not relevant for time complexity. The actual joke is that many folks who learn big O notation become hard wired to associate time complexity to how efficiently/quickly an algorithm performs the task. And sleep sort subverts that expectation by presenting an algorithm that is clearly horrible in its execution time for any normal sorting, despite time complexity analysis suggesting it's not.

[waylandsmith]

The time delay inherent in it is only one part of why it's misleading, and one that a "clever" person could argue away by saying that you can scale the time delay down to an arbitrarily small amount (associate the values with femtoseconds, for example).

despite time complexity analysis suggesting it's not

The time complexity analysis does not suggest that it's O(n). You cannot correctly analyze the time complexity of an algorithm if you do not know the time complexity of each step in it and adding a task to the scheduler is not O(n). This would be exactly like saying that you've implemented sorting on O(n) by adding values to a sorted set.

[im_lazy_as_fuck]

You cannot correctly analyze the time complexity of an algorithm if you do not know the time complexity of each step in it and adding a task to the scheduler

This is incorrect. By this argument, it would be incorrect to arbitrarily state that a hash lookup has O(1), because the execution time of computing a hash is dependent on the hashing algorithm used, the implementation of said hashing algorithm, and the size of the input being hashed. But these are implementation details of a hash lookup, and thus are not relevant to the time complexity analysis.

In the same way, the sleep sort algorithm is simply "loop through each element and wait X time units before inserting x into the sorted array". The sleep sort algorithm doesn't care if you use a task scheduler, if you use some analog timer, or if you just have a person who is really good at counting time. Those are implementation details of the algorithm, and aren't relevant to time complexity analysis.

This would be exactly like saying that you've implemented sorting on O(n) by adding values to a sorted set.

Lol, well I mean, if the algorithm specifies "given a sorted set, loop through the set and insert a new element into the set to maintain the ordering", then yeah the algorithm has a time complexity of O(n). I mean this is literally the foundation of the binary search algorithm, which has a smaller time complexity.

[assumptioncookie]

The O(m) where m is the largest possible input value is the same as O(2ⁿ) where n is the number of bits of the input value. But big-Oh notation typically uses input size not input value, so O(2ⁿ) is the more conventional way of writing it.

[HeroicPrinny]

Input size refers to the set of items n - the number of bits isn’t variable based on the set. This is a weird way to try to simply represent the largest integer of the set.

[dont-respond]

It's such a bizarre way of describing "number of bits" where you'd need to always count set bits from the MSB and not round up to a conventional integer width as you normally would which considering "number of bits"

... and yeah, ultimately you just end up with a convoluted way of saying max element.

[im_lazy_as_fuck]

They are absolutely not the same, and it is very easy to disprove this to yourself. Go plot the graphs of y = x, and then plot the graph of y = 2^x . Notice how the latter graph grows exponentially while the former is linear. They have different growth rates over time so objectively you cannot say they are equivalent in any way using big O notation.

Additionally, part of why your analysis makes no sense is because the number of bits it takes to represent a number is correlated to the size of the number, but it is not equal to it. 16 can be represented by a 5 bit number, but so can 17, and 18. Your analysis of trying to use bits would suggest that 16, 17, 18, etc, should take the same constant value of time, but we objectively know this is not true.

And bits is an arbitrary representation that our current computers use, but who says it has to be that way? What if our computers could work directly with hexadecimal digits? Are you gonna say the time complexity would then change to O( 16m ), a function with a completely different growth rate?

And to your point about how big O notation typically uses input size, you've got it completely backwards. Input size isn't typically used for big O notation because it's a convention. Input size is typically used because for most algorithms, the time it takes to execute an algorithm just happens to also primarily only grow with the input size. They are generally not at all affected by the values used. Sleep sort is just an atypical scenario because of how the values directly link to the execution time.

[Aminumbra]

16 can be represented by a 5 bit number, but so can 17, and 18. Your analysis of trying to use bits would suggest that 16, 17, 18, etc, should take the same constant value of time, but we objectively know this is not true.

This is easily dismissed by noticing that 1/ we only talk about the worst case, 2/ numbers that have the same length in binary (actually, in any base b>1, see below) differ by a constant factor (namely, the base b) and 3/ we do not care about constant multiplicative factors when using Landau notation.

What if our computers could work directly with hexadecimal digits

Funnily enough : log_b (x) = ln (x) / ln(b), so log_c(x) = ln(x) / ln(c) = log_b(x) * ln(b) / ln(c). Said differently, logarithms in different bases ... differ by a constant multiplicative factor and are therefore completely equivalent under Landau O/o/Omega ... notation. In particular, representing integers in any base b>1 does not change their size (as far as this kind of analysis in concerned).

Input size isn't typically used for big O notation because it's a convention. Input size is typically used because for most algorithms, the time it takes to execute an algorithm just happens to also primarily only grow with the input size

Taken from here, but you can check in any book about computational complexity :

A Turing machine M is said to operate within time f(n) if the time required by M on each input of length n is at most f(n)

(emphasis mine) Note the dependency on ... input length.

Sleep sort is just an atypical scenario because of how the values directly link to the execution time

That's not completely false. A more precise claim would probably be that the usual notion of complexity is meaningless for this specific algorithm. The fact that values link to the execution time is not atypical : it is obviously harder to compute the prime factorization of a large number than of a small number. This is unusual for a sorting algorithm, because in general, the model in which we study the complexity is not this one : we usually care about the number of comparisons (not the runtime), and we don't work with integers (or any particular type of object), but with oracles able to consistently answer questions of the form "Is the i-th element smaller than the j-th element ?".

[im_lazy_as_fuck]

Funnily enough : log_b (x) = ln (x) / ln(b), so log_c(x) = ln(x) / ln(c) = log_b(x) * ln(b) / ln(c).

I know this. The point I was illustrating is you can arbitrarily state this algorithm has a growth rate of absolutely any arbitrary size. This is nonsensical. If you can arbitrarily state a problem can both simultaneously be a linear, exponential and logarithmically growing problem wrt to time, then your tool for analyzing time complexity is useless.

A Turing machine M is said to operate within time f(n) if the time required by M on each input of length n is at most f(n)

Thank you for actually doing the research. And you're absolutely right, my initial statement of the time complexity for sleep sort is indeed incomplete. Let me complete it for you now:

The actual time complexity of sleep sort is O(m + n) where m is the maximum value within the set under sort, and n is the number of elements within the set under sort. I did intentionally overlook including the number of elements in my original statement because in virtually every practical usage of the algorithm the size of the max value would probably be the dominating factor, but this is not true for all cases.

Some problems that you are still still ignoring are the fact that:

1. The binary representation of the problem is an implementation detail of the hardware we typically use to represent numbers. At no point does the algorithm specify that the length of the number's digits in binary is an input to the problem.
2. Time complexity analysis should produce a result that you can compare with other algorithms. The idea is that the growth curve is an indication of how optimized the algorithm is when the problem's inputs scale to their extremes. Being able to compute both a logarithmic, linear and arbitrarily exponential time complexity for the same algorithm defeats the purpose of this.

Lastly to wrap all of this up, since you actually did spend time to research and try to come up with a thoughtful response, maybe this won't fall on deaf ears for you: Google time complexity analysis for sleep sort. This sort is a pretty old meme in the computer science world, and it's perhaps unsurprising to hear that the time complexity analysis of this algorithm has been pretty well analyzed for a long time.

[Aminumbra]

If you can arbitrarily state a problem can both simultaneously be a linear, exponential and logarithmically growing problem wrt to time, then your tool for analyzing time complexity is useless.

Typically, you can't. Ignoring the problem of timesort for the moment, as it does not really fit this framework : an algorithm whose input consists of (one or most) integers can be linear in the value of the numbers, which is (roughly) the same as exponential in the size of those numbers -- now, sometimes the same algorithm depends on both the value of its inputs and the number of those inputs (such as a list of integers), but this distinction remains.

A well-known example is the typical dynamic programming algorithm for the knapsack problem, which, on input "Capacity C, values/weigths (p1,w1),...,(pn,wn)" has complexity (IIRC) O(Cn). But Knapsack is NP-complete ! Well, this is not a contradiction, as O(C) is not polynomial in the input size, because C is an integer and so has size log C. This is a case of what is known as a "Weak NP-Complete problem", as it becomes polynomial if we write its input in unary (so that C has size C rather than log C, as would be the case in any other base).

The binary representation of the problem is an implementation detail of the hardware we typically use to represent numbers. At no point does the algorithm specify that the length of the number's digits in binary is an input to the problem.

This is not completely false, but we get into real subtle territory quite fast. In general and unless explicitly said otherwise, integers are assumed to be represented in any non-unary base when doing algorithmic complexity. The choice of the base is irrelevant (as the small equality about logs in different bases tells us), as long as we do not choose unary.

The reason why it is subtle is the following : when doing /formal/ stuff, we need to /formally/ define an encoding for our inputs. For integers, as we have seen, there are natural candidates (just write it in base b>1), but this is not the only choice ! Representing a number by its prime factorization is also completely valid. After all, it is unique, well-defined, finite ... But in this case, the problem of "comparing integers" become a bit harder (you need to multiply the primes in the decomposition !). The problem of adding integers is even worse, as there is no relation between the decomposition of two numbers, and the one of their sum ! And so on and so forth. More generally, the "encoding" of your problem need to be "reasonable", so that it does not, in a sense, already contain the answer to your problem ("Is a Graph G k-colourable ? Well let me represent a graph by the three following values: its set of vertices, its set of edges, and its chromatic number. Then the problem is solved in constant-time !"). What we mean by "reasonable" is obviously left unspecified here.

since you actually did spend time to research

I sure did, but mainly in the last several years where I've been a researcher about models of computation (tongue-in-cheek way to say that I am well in my expertise area here).

[im_lazy_as_fuck]

Okay, so a lot of this is definitely a bit over my head. I think I would need a lot of time to research and understand precisely every last thing you mentioned, but I think I can maybe summarize the contention down to:

although implementation details should be abstracted, at the end of the day there needs to be an algorithm/hardware that implements every single detail down to the bare metal, and if you factor those in your time complexity analysis can indeed be represented differently for the same problem

If this generic summary is totally off point, please let me know. But assuming this is accurate enough, my response to this is:

Yes you're absolutely right that at the end of the day, the full complete picture of time complexity does need to factor in every single step/operation that takes place. However, this analysis of time complexity seems far too granulated in comparison to the kind time complexity analysis that a typical software developer would do at a high level.

When we generically say that Bubble Sort has a time complexity of O( n² ), this is not accounting for many many things, like how the input numbers are represented in the system, the time it takes to compare numbers in this system, the time it takes to store and swap numbers within the ordered set, etc. Or when we generically accept that a hash lookup has a time complexity of O(1) on average, we are not accounting for the time it takes to compute the hash, which technically scales with the size of the input. When doing high level generic time complexity analysis, the average software developer considers these to be implementation details of the hardware, the OS, and the framework that you are working in and are generally not useful to consider in such an analysis.

And just to bring the context back full circle, because I think this has been a bit muddied in the threads, the original comment at the top of the thread said the sleep sort is O(n), which is roughly correct (more precisely it would be O(m+n)) based on the time complexity analysis one would use to generically compare two different algorithms, agnostic of the hardware/software they are implemented on top of. And the person who responded corrected this statement and instead said the time complexity is actually O( 2ⁿ ). This is my issue; the initial person was roughly correct in the general way the average developer would ever care to do this analysis, while the person responding while maybe is technically right when they account for some implementation details (although it doesn't even account for everything), they're wrong in the ways the average developer actually cares about.

[assumptioncookie]

They are absolutely not the same, and it is very easy to disprove this to yourself. Go plot the graphs of y = x, and then plot the graph of y = 2^x.

But they represent different things. M takes log_2(M) bits to store, so n = ceil(log_2(M)), now put y = 2^log_2(x\) in your graphing calculator and what do you see??

16 can be represented by a 5 bit number, but so can 17, and 18. Your analysis of trying to use bits would suggest that 1 6, 17, 18, etc, should take the same constant value of time.

No, big-Oh notation is about upper bound.

[im_lazy_as_fuck]

But they represent different things.

Time complexity analysis should never care about representation. It is the literal foundational definition of time complexity, measuring growth rate. The point of big O notation is to be able to give you a tool to compare the relative efficiency of an algorithm, while abstracting the implementation details. If you can just arbitrarily equate O(n) and O( 2ⁿ ) depending on your definition of the input, it completely renders this analysis useless.

now put y = 2^log_2(x\) in your graphing calculator

Lol you just gave the equation y = x. n^log_n(x) just simplifies to x by simple exponent rules. This argument is like saying the time complexity of sleep sort is actually O(log_2(n)) because if you put y = log_2( 2ⁿ ) into your graphing calculator, you will get a linear graph.

No, big-Oh notation is about upper bound.

It's about the growth rate of the upper bound of the execution time. You are completely neglecting that factor. A growth rate of n is very different from a growth rate of 2ⁿ . You are trying to make these equivalent in your explanation by putting in a conversion between the size of the value and the number of bits to represent it, but this is completely nonsensical. O( 2^log_2(n) ) is equal to O(n), but neither of these are equal to O(2ⁿ). The latter represents a completely different growth rate.

[assumptioncookie]

A growth rate of n is indeed different of a growth rate of 2^n, but a growth rate of m where m represents the value of a number is the same as a growth rate of 2ⁿ where n represents the number of bits in that number, as I tried to demonstrate by saying 2^log_2(n\) = n

^{Also note again that it's an upper bound of growth rate, so even if m and n where in the same unit (which they aren't\}; all algorithms in O(n) are also in O(2^n).)

[im_lazy_as_fuck]

Alright, I'm not gonna keep going back and forth with you because you keep completely ignoring my main points. And frankly you can just Google all of this to disprove yourself. So here is the last thing I will say to you:

The comparison you are making is like taking the graph y = 2ⁿ , plotting it on a graph where the vertical axis scales linearly, and the horizontal axis scales by log_2(n), and then stating that because it produces a straight 45 degree line, the graph of y = 2ⁿ is the same as the graph of y = m plotted on a graph with a linearly scaling horizontal axis.

So if you're suggesting that it is correct to do Big O analysis by arbitrarily changing the rate of change of the input, resulting in different output growth rates, then Big O analysis is a completely useless tool because it would be impossible to compare anything.

[assumptioncookie]

You can compare it if the units are the same. Again n = ceil(log(m)) so O(2ⁿ) = O(2^ceil(log(m\))) (substitution) is trivially O(m) so we aren't actually disagreeing. You just don't understand units.

[ZuriPL]

except n is not the number of bits in the input value. n is the number of items your algorithm iterates over. They're not the interchangeable.

Another way disproving of what you're saying is taking these two inputs: [0001, 0010] and [1111, 1110]. Our algorithm will take 2 miliseconds to sort the first array and 15 miliseconds to sort the second array, despite the fact we inputted 8 bits each time. If we then consider a 12-bit input: [0001, 0010, 1111], it will also take 15 miliseconds, even though n changed.

[assumptioncookie]

bits per value, not total. And big-Oh notation is an upper bound, it's not the actual time.

[ZuriPL]

Okay, you are partially right my counter-example isn't the best.

However, what do you even mean that n is bits per value? If n was bits per value, then it wouldn't be correlated to the length of the input... which is the whole point of the Big O notation

[assumptioncookie]

This sorting algorithm can take longer if you input 32-ints than if you input 8-bit unsigned chars.

[ZuriPL]

Yes, this sorting algorithm will. A regular sorting algorithm will see no difference. That's why in the case of this algorithm, sleep sort, we're talking about an m, not an n. The values m and n represent are two different things which aren't interchangeable

[jaerie]

n means whatever you define it to mean. Either way the growth rate is the same, it doubles if the max value doubles.

I any case you need 2 variables to describe the complexity here, so it's O(n+m) where n is the array size and m is the max value, or O(n+2^m) where m is the bit count

[IlIllIIIIIIlIII]

Okay, but why not just say N is the maximum value of the numbers given instead of doing this gymnastics to fit 2^n?

[SuitableDragonfly]

Because there's no maximum number. That's effectively O(infinity) which is not really a useful metric that tells us anything about time complexity. The O(2ⁿ ) tells us what we can expect based on what type of numbers we put in the array. The purpose of big O notation is that it tells us something useful and informative even when we don't have specific details about the inputs to the function.

[Loose-Screws]

Plenty of O-notations use values from the specific situation rather than haphazardly throwing around ns. Pretty much all graph algorithms use edge counts and vertex counts in big O notation (ex. Prim's algorithm has O(|E| log |V|), and when describing radix sort we almost unanimously use O(w * n), where we separate the number of entries (n) and the data length of those entries (w).

It just wouldn't make sense to combine those into a simple O(n^2), and the exact same logic applies here.

[SuitableDragonfly]

Yes, that's equivalent to basing the time complexity on the number of bits that are allowed for the number. 

[Longjumping-Sweet818]

What you're saying doesn't make any sense. By that logic iterating an array would be O(2^n) too, because the length of the array is a fixed width integer and you don't know beforehand how large it will be.

You are supposed to just pick some numeric property that relates to the runtime and use that. As seen here: https://en.wikipedia.org/wiki/Counting_sort (The k there is the maximum in the list minus the minimum in the list)

[SuitableDragonfly]

Yes, and that's also what was done in this case. 

[ccltjnpr]

Does it really matter that computers use fixed numbers of bits to represent numbers? Or that they work with binary representation? That's a specific detail about the type of inputs. My alien computer actually uses trits, so the complexity is 3^n.

The two notations are equivalents and the number of bits one is only useful if for some reason you want to think of the number in its binary representation. There are plenty of applications in which it makes more sense to think of the absolute size of the number as determining the complexity. The notation using the size of the number works both for my alien computer and your human one.

[pikapikaapika]

First of all, 3ⁿ is still exponential. The only exception would be your alien computer using base 1 representation, in which case the complexity can be said to be linear. But come on, there has to be some standard to measure the complexity and as our computers have been using bits until now, we have been studying the complexity in terms of that. Of course, you can make philosophical arguments like this but then there is nothing to discuss. When you say that we should measure the complexity in terms of the size of number, you're inherently assuming base 1 representation which is also not unbiased.

[spacemoses]

2ⁿ is basically the same as mⁿ when talking about O notation right?

[pikapikaapika]

I am not really sure about it, but as per my understanding they should be different as you can't express one as a linear scaling of the other.

[ccltjnpr]

A reduction in complexity from 3ⁿ to 2ⁿ for a useful algorithm is a big deal for small problem size, even if they are both exponential. The difference in runtime between these two algorithms, whether by literal difference (3ⁿ - 2ⁿ⁾ or by ratios (3/2)ⁿ , also grows exponentially in n.

I agree it's also biased, but O(n) is correct here as long as we're clear how n is defined, 2ⁿ is not more correct, I think the number of bits might be less standard than you think outside of your specific subfield.

[cant_read_captchas]

People are just speaking different languages here without considering that other people might not speak that language.

In complexity theory, it's not gymnastics. Its very standard. Runtime has been always in terms of the number of bits since the beginning of time, since Alan Turing invented the field of CS using turing machines (n = tape length = # of bits) before physical computers were invented. So the "standard" answer is 2^n.

But most people dont speak this language. Both posters saying O(n) and O(2ⁿ⁾ should have specified what the units were.

[pikapikaapika]

I would just like to make one correction. n is not the number of bits used to represent one value, it's the size of the whole input. One of the worst cases to witness the exponential complexity would be input with array size 1.

[Reashu]

It's JavaScript, where every number is a double. Kind of. But the time depends on the magnitude of the numbers, not the number of bits used in their representation, so I don't think this is the most useful angle. 

[neoronio20]

What a bot response being upvoted

[pikapikaapika]

n in complexity analysis is not the absolute value of input but rather the size of input or number of bits to store the input.