4 ms·

To risk killing the joke: when I said "constant time", I alluded to the words and art of time complexity analysis but actually did not mean to go there. This is

by xena 3y ago

To risk killing the joke: when I said "constant time", I alluded to the words and art of time complexity analysis but actually did not mean to go there. This is a double entendre that uses two conflicting views of the word "time" because yes it is impossible to make a sorting algorithm constant time in complexity analysis terms. The joke is that the actual intent of the statement is wall clock time. This is the time that is more relevant in job interviews (and realistically when people pull the "write an integer sort function" thing out of their ass for me to defecate code onto the screen, they don't use numbers smaller than like 100, meaning that this program will be almost perceptually instant to run). It's a subtle metalinguistic joke. It's supposed to poke fun at understandings of how computer science works by turning them on their head. I'm sorry the joke didn't land on you.

ctenb 3y ago
Can the wall time be considered constant if it depends on the magnitude of the numbers to sort? A list of numbers between 1 and 1000 will be much faster to sort than a list of numbers between 1 and 10^100. EDIT: I did get the joke when I read your post, and laughed to myself, so well done :)
- xena 3y ago
  The constant is the biggest number in the list multiplied by the sleep multiplicand. That plus overhead gets you the approximate runtime of the function.
  - ctenb 3y ago
    Yeah, but technically that doesn't qualify as a constant since it depends on the input. If you explicitly constrain the problem space such that the magnitude of the numbers in the list is bounded by a fixed upper bound, then it works out. That's fine though, but then it's not a fully general sorting algorithm, like e.g quicksort
  - Tainnor 3y ago
    If you just repeat the same number a million times, then the threads will all be scheduled to run at the same time, but of course, your computer doesn't have a million cores, so the threads will have to be executed partially in sequence. That means, even if you assume the largest integer is a constant (valid for some integer types, but notably not Integer in Haskell), the runtime will be proportional to the number of elements in the list.
Tainnor 3y ago
It's not a "subtle metalinguistic joke". You're just redefining words. The algorithm isn't constant in complexity theory terms and it's also not constant in "wall-clock time" (I'm not sure why you think the two are unrelated?), except if you use a model of computation that is so bonkers that it would be of no value. Maybe it works as a sort of dadaistic literature, like the ones where they redefine "chair" to mean "table" and so on, but beyond that? Both your article and this comment of yours show that you're annoyed at algorithmic interview questions, so you're trying (well, at least in this fantasy) to one-up your interviewers by being smarter, and technically correct, but in an unexpected way. I understand the sentiment, but unfortunately, this only works when you're actually at least technically correct.

by xena 3y ago

ctenb 3y ago

Can the wall time be considered constant if it depends on the magnitude of the numbers to sort? A list of numbers between 1 and 1000 will be much faster to sort than a list of numbers between 1 and 10^100. EDIT: I did get the joke when I read your post, and laughed to myself, so well done :)

xena 3y ago
The constant is the biggest number in the list multiplied by the sleep multiplicand. That plus overhead gets you the approximate runtime of the function.
- ctenb 3y ago
  Yeah, but technically that doesn't qualify as a constant since it depends on the input. If you explicitly constrain the problem space such that the magnitude of the numbers in the list is bounded by a fixed upper bound, then it works out. That's fine though, but then it's not a fully general sorting algorithm, like e.g quicksort
- Tainnor 3y ago
  If you just repeat the same number a million times, then the threads will all be scheduled to run at the same time, but of course, your computer doesn't have a million cores, so the threads will have to be executed partially in sequence. That means, even if you assume the largest integer is a constant (valid for some integer types, but notably not Integer in Haskell), the runtime will be proportional to the number of elements in the list.

Tainnor 3y ago

It's not a "subtle metalinguistic joke". You're just redefining words. The algorithm isn't constant in complexity theory terms and it's also not constant in "wall-clock time" (I'm not sure why you think the two are unrelated?), except if you use a model of computation that is so bonkers that it would be of no value. Maybe it works as a sort of dadaistic literature, like the ones where they redefine "chair" to mean "table" and so on, but beyond that? Both your article and this comment of yours show that you're annoyed at algorithmic interview questions, so you're trying (well, at least in this fantasy) to one-up your interviewers by being smarter, and technically correct, but in an unexpected way. I understand the sentiment, but unfortunately, this only works when you're actually at least technically correct.