5 ms·

I found this part of the code quite funny: # If there are < 5 items, just return the median if len(l) < 5: # In this case, we fall back on the

I found this part of the code quite funny: # If there are < 5 items, just return the median if len(l) < 5: # In this case, we fall back on the first median function we wrote. # Since we only run this on a list of 5 or fewer items, it doesn't # depend on the length of the input and can be considered constant # time. return nlogn_median(l) Hell, why not just use 2^140 instead of 5 as the cut-off point, then? This way you'd have constant time median finding for all arrays that can be represented in any real-world computer! :) [1] [1] According to https://hbfs.wordpress.com/2009/02/10/to-boil-the-oceans/ https://hbfs.wordpress.com/2009/02/10/to-boil-the-oceans/

SkiFire13 2y ago
Ultimately when an algorithm has worse complexity than another it might still be faster up to a certain point. In this case 5 is likely under that point, though I doubt 2^256 will. In practice you might also want to use a O(n^2) algorithm like insertion sort under some threshold.
- someplaceguy 2y ago
  > Ultimately when an algorithm has worse complexity than another it might still be faster up to a certain point. Sure, but the author didn't argue that the simpler algorithm would be faster for 5 items, which would indeed make sense. Instead, the author argued that it's OK to use the simpler algorithm for less than 5 items because 5 is a constant and therefore the simpler algorithm runs in constant time, hence my point that you could use the same argument to say that 2^140 (or 2^256) could just as well be used as the cut-off point and similarly argue that the simpler algorithm runs in constant time for all arrays than can be represented on a real-world computer, therefore obviating the need for the more complex algorithm (which obviously makes no sense).
  - thrw2486776 2y ago
    If you set n=2^140, then sure, it’s constant. If instead you only have n<=2^140, then n varies across a large set and is practically indistinguishable from n<=infinity (since we get into the territory of the number of atoms in the universe), therefore you can perform limit calculations on it, in particular big O stuff. In the article n was set to 5. All of those arrays (except maybe 1) have exactly 5 elements. There is no variance (and even if there was, it would be tiny, there is no point in talking about limits of 5-element sequences).
    - someplaceguy 2y ago
      > In the article n was set to 5. All of those arrays (except maybe 1) have exactly 5 elements. There is no variance No, the code was: # If there are < 5 items, just return the median if len(l) < 5: return nlogn_median(l) > and even if there was, it would be tiny, there is no point in talking about limits of 5-element sequences So your point is: not all constants are created equal. Which circles all the way back to my original point that this argument is pretty funny :)
raincole 2y ago
Big-O notation and "real-world computer" don't belong to the same sentence. The whole point of big-O notation is to abstract the algorithm out of real-world limitations so we can talk about arbitrarily large input. Any halting program that runs on a real world computer is O(1), by definition.
- someplaceguy 2y ago
  > The whole point of big-O notation is to abstract the algorithm out of real-world limitations so we can talk about arbitrarily large input. Except that there is no such thing as "arbitrarily large storage", as my link in the parent comment explained: https://hbfs.wordpress.com/2009/02/10/to-boil-the-oceans/ https://hbfs.wordpress.com/2009/02/10/to-boil-the-oceans/ So why would you want to talk about arbitrarily large input (where the input is an array that is stored in memory)? As I understood, this big-O notation is intended to have some real-world usefulness, is it not? Care to elaborate what that usefulness is, exactly? Or is it just a purely fictional notion in the realm of ideas with no real-world application? And if so, why bother studying it at all, except as a mathematical curiosity written in some mathematical pseudo-code rather than a programming or engineering challenge written in a real-world programming language? Edit: s/pretending/intended/
  - raincole 2y ago
    > (where the input is an array that is stored in memory)? If the input is an array that is stored in a piece of real-world memory, then the only possible complexity is O(1). It's just how big-O works. Big-O notation is an abstraction that is much much closer to mathematics than to engineering. > this big-O notation is pretending to have some real-world usefulness... Big-O notation is not a person so I'm not sure whether it can pretend something. CS professors might exaggerate big-O notation's real-world usefulness so their students don't fall asleep too fast. > fictional Theoretical. Just like the other theoretical ideas, at best big-O notation gives some vague insights that help people solve real problems. It gives a very rough feeling about whether an algorithm is fast or not. By the way, Turing machine is in this category as well.
  - fenomas 2y ago

SkiFire13 2y ago

Ultimately when an algorithm has worse complexity than another it might still be faster up to a certain point. In this case 5 is likely under that point, though I doubt 2^256 will. In practice you might also want to use a O(n^2) algorithm like insertion sort under some threshold.

someplaceguy 2y ago
> Ultimately when an algorithm has worse complexity than another it might still be faster up to a certain point. Sure, but the author didn't argue that the simpler algorithm would be faster for 5 items, which would indeed make sense. Instead, the author argued that it's OK to use the simpler algorithm for less than 5 items because 5 is a constant and therefore the simpler algorithm runs in constant time, hence my point that you could use the same argument to say that 2^140 (or 2^256) could just as well be used as the cut-off point and similarly argue that the simpler algorithm runs in constant time for all arrays than can be represented on a real-world computer, therefore obviating the need for the more complex algorithm (which obviously makes no sense).
- thrw2486776 2y ago
  If you set n=2^140, then sure, it’s constant. If instead you only have n<=2^140, then n varies across a large set and is practically indistinguishable from n<=infinity (since we get into the territory of the number of atoms in the universe), therefore you can perform limit calculations on it, in particular big O stuff. In the article n was set to 5. All of those arrays (except maybe 1) have exactly 5 elements. There is no variance (and even if there was, it would be tiny, there is no point in talking about limits of 5-element sequences).
  - someplaceguy 2y ago
    > In the article n was set to 5. All of those arrays (except maybe 1) have exactly 5 elements. There is no variance No, the code was: # If there are < 5 items, just return the median if len(l) < 5: return nlogn_median(l) > and even if there was, it would be tiny, there is no point in talking about limits of 5-element sequences So your point is: not all constants are created equal. Which circles all the way back to my original point that this argument is pretty funny :)

raincole 2y ago

Big-O notation and "real-world computer" don't belong to the same sentence. The whole point of big-O notation is to abstract the algorithm out of real-world limitations so we can talk about arbitrarily large input. Any halting program that runs on a real world computer is O(1), by definition.

someplaceguy 2y ago
> The whole point of big-O notation is to abstract the algorithm out of real-world limitations so we can talk about arbitrarily large input. Except that there is no such thing as "arbitrarily large storage", as my link in the parent comment explained: https://hbfs.wordpress.com/2009/02/10/to-boil-the-oceans/ https://hbfs.wordpress.com/2009/02/10/to-boil-the-oceans/ So why would you want to talk about arbitrarily large input (where the input is an array that is stored in memory)? As I understood, this big-O notation is intended to have some real-world usefulness, is it not? Care to elaborate what that usefulness is, exactly? Or is it just a purely fictional notion in the realm of ideas with no real-world application? And if so, why bother studying it at all, except as a mathematical curiosity written in some mathematical pseudo-code rather than a programming or engineering challenge written in a real-world programming language? Edit: s/pretending/intended/
- raincole 2y ago
  > (where the input is an array that is stored in memory)? If the input is an array that is stored in a piece of real-world memory, then the only possible complexity is O(1). It's just how big-O works. Big-O notation is an abstraction that is much much closer to mathematics than to engineering. > this big-O notation is pretending to have some real-world usefulness... Big-O notation is not a person so I'm not sure whether it can pretend something. CS professors might exaggerate big-O notation's real-world usefulness so their students don't fall asleep too fast. > fictional Theoretical. Just like the other theoretical ideas, at best big-O notation gives some vague insights that help people solve real problems. It gives a very rough feeling about whether an algorithm is fast or not. By the way, Turing machine is in this category as well.
- fenomas 2y ago