4 ms·
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
by 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 agoThe 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 agoYeah, 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 agoIf 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.