7 ms·

I think there's some good info in this article covered by various degrees of misinformation. For some reason, the article starts off with this totally wrong def

I think there's some good info in this article covered by various degrees of misinformation. For some reason, the article starts off with this totally wrong definition of big-O, and proceeds to make conclusions with this wrong definition. Let me provide the accurate definition: The statement "f is O(g)" means there exists some input, call it t, such that for every x >= t, it only takes some constant multiplier M (i.e., constant in x) to always have g absolutely no smaller than f. In notation: |f(x)| <= M * |g(x)|, where x is at least t. This bit about "x is at least t" is very important and notifies us that this is "asymptotic behavior". It does not make a difference how wacky or weird f is compared to g below t. It can contain all these crazy memory hierarchy artifacts, it could contain a short burst of exponential slowdown, it could contain anything. Furthermore, according to the above definition, big-O has nothing to do with any tangible quantity whatsoever. It's a method for comparing functions. The functions may represent whatever is of tangible or intangible interest: memory, time, money, instructions, ... Big-O analysis usually posits that the details below t aren't the details that matter. (Of course, there are situations where they do, but in such you would not use big-O.) If you want to have some analysis that is global, you don't need asymptotic analysis (though it might help as a start). You can just talk about functions that are strictly greater than or less than your function of interest everywhere. But these analyses are difficult because a much higher level of understanding of your function of interest is required.

zeroer 10y ago
The author gets the definition of big-O completely backwards. Every single time the author says "Big-O" he means "little-o". Here are the definitions: https://cathyatseneca.gitbooks.io/data-structures-and-algorithms/content/analysis/notations.html https://cathyatseneca.gitbooks.io/data-structures-and-algori... Basically, big-O is a claim that your process is at least -this- fast. Small-o is a claim that your process can't be faster than -this-. He means the latter. > Still not convinced? Think I'm misunderstanding Big-O? Yea, I do.
- jo909 10y ago
  Please see https://en.wikipedia.org/wiki/Best,_worst_and_average_case https://en.wikipedia.org/wiki/Best,_worst_and_average_case Big-O is valid notation for _many aspects_ of an algorithm. The author applied it to a very practical one and explained what exactly he describes very well.
  - reikonomusha 10y ago
    I think it's a massive and needless abuse of standard computer science terminology to re-define it as something completely different.
    - MrManatee 10y ago
      I'm not entirely sure what you are referring to. You might be referring to the fact that the author's definition of big-O doesn't say anything about constant factors or asymptotics. This makes the definition incorrect, or at least sloppy. But judging by usage, it seems that he actually knows and is using the standard definition. The error is just in that one sentence, and it doesn't affect the rest of the argument. You might also be objecting to the fact that he makes a distinction between time and instruction count, and is using big-O notation for both. I don't think there's anything nonstandard about making this distinction when it needs to be made. Take, for example, Karmarkar's algorithm: https://en.wikipedia.org/wiki/Karmarkar%27s_algorithm https://en.wikipedia.org/wiki/Karmarkar%27s_algorithm
  - DanWaterworth 10y ago
    Re-read the article, bearing in mind that O(sqrt n) is a set that contains O(1).
    - angry_octet 10y ago
      Yes, but it isn't very helpful to think of it that way, we're not competing to find the weakest constraint.
  - zeroer 10y ago
    The best/worst/average issue is orthogonal to the definition of what big-O means. The time it take an algorithm has best/worst/average cases, and each of these is a function and thus is a member of big-O classes. The definition of big-O has a completely standardized and unambiguous definition, and the author of the article somehow has a four-part blog post on big-O without knowing it.
- smallnamespace 10y ago
  You're right, but almost all colloquial usage of Big-O seems to be close to theta-O because people pick the tightest bound they can. That's why everyone writes that comparison sorts are O(n lg N), even though it's also technically O(exp N) as well.
  - zeroer 10y ago
    Yea, I thought about that, but he doesn't mean theta, either. What he's giving is a physical impossibility proof -- you can't do memory access better than sqrt(N). When he gives a physical example of a machine of arbitrary size that accesses memory in sqrt(N) time, then we can talk about theta.
    - Animats 10y ago
      Well, cube root of N; you can stack memory. The speed of light limitation on distance to DRAM memory is real, but so far seems to affect mostly supercomputers. Are there any large server boards where speed of light lag is the limit on memory capacity?
      - zeroer 10y ago
        Read part two of the article. You can't stack memory indefinitely -- you'll get a black hole.
  - perfectfire 10y ago
    > it's also technically O(exp N) as well. I wonder if this is what one interviewer was trying to get at when he asked me over and over again if a binary search was worst case O(log N). I just kept saying that if you took more than log N steps to perform a binary search then you by definition did not perform a binary search. He was off his rocker so I kind of doubt he was looking for the difference between little-o, theta, and big-O. It's good stuff to remember and might impress a more sane interviewer some day though.
- rntz 10y ago
  Your claims about what little-o and big-O mean don't match the explanation at https://cathyatseneca.gitbooks.io/data-structures-and-algorithms/content/analysis/notations.html https://cathyatseneca.gitbooks.io/data-structures-and-algori... That page says o(f) == O(f) and not Theta(f). When you say "small-o is a claim that your process can't be faster than -this-", that seems to match the definition of Omega(f). Did you mean that the author should have used big-Omega? As a side-note, I've always thought that {big-O,Theta,Omega,small-o} notation was very confusing. We should just have a notation for "the asymptotic equivalence class of a function", let's say A(f). Then to say f \in O(g), we say A(f) <= A(g). To say f \in Theta(g), we say A(f) = A(g). f \in o(g) becomes A(f) < A(g). And so forth. Instead of lots of new notation, we add a single function A and re-use notation for orderings which everyone already knows. (Of course, I'm omitting the definition of the ordering on these equivalence classes, so maybe there is some difficulty in defining that...)
  - contravariant 10y ago
    >As a side-note, I've always thought that {big-O,Theta,Omega,small-o} notation was very confusing. We should just have a notation for "the asymptotic equivalence class of a function", let's say A(f). Then to say f \in O(g), we say A(f) <= A(g). To say f \in Theta(g), we say A(f) = A(g). f \in o(g) becomes A(f) < A(g). And so forth. Instead of lots of new notation, we add a single function A and re-use notation for orderings which everyone already knows. (Of course, I'm omitting the definition of the ordering on these equivalence classes, so maybe there is some difficulty in defining that...) Your A is pretty much equivalent to \Theta. Saying f \in \Theta(g) is equivalent to saying \Theta(f) = \Theta(g). Edit: as an aside O(f) = O(g) is also equivalent to f \in \Theta(g), and O(f) \subset O(g) is equivalent to f \in O(g).
    - rntz 10y ago
      For equality, yes, Theta works! But I care not just about equality but about comparison. In particular, it would be nice if the "natural" ordering on A(f) had the property that A(f) <= A(g) iff f is O(g) Theta(g) is a set, and the most natural ordering on sets is subsetting/inclusion. However, Theta(x) is not a subset of Theta(x^2), even though x is O(x^2)! So the natural ordering on sets doesn't do what I want. It might be possible to define an ordering on Theta-classes that does what I want, though. Edit: I just saw your comment about O. I think O might just work! So instead of remembering big-O, Theta, and Omega, I can just use O(f) <= O(g) for f is O(g) O(f) = O(g) for f is Theta(g) O(f) >= O(g) for f is Omega(g) Is that true? (I think small-o might be slightly more complicated, unfortunately. It has a more unusual definition: https://en.wikipedia.org/wiki/Big_O_notation#Little-o_notation https://en.wikipedia.org/wiki/Big_O_notation#Little-o_notati...)
smallnamespace 10y ago
> It does not make a difference how wacky or weird f is compared to g below t. It can contain all these crazy memory hierarchy artifacts, it could contain a short burst of exponential slowdown, it could contain anything. Yes, but if you continue reading the next post, the author is essentially arguing that the cache hierarchy extends indefinitely due to 1) the speed of light and 2) the amount of information that can fit within a light cone of a certain radius. In that case, cache hierarchy effects aren't 'weird things that happen below t', they represent the asymptotic behavior we can expect due to the laws of physics, no matter how far out to the right we go.
- rosalinekarr 10y ago
  Worrying about the speed of light in processor caching these days is like putting a spoiler on your cart and horse to reduce drag. It might matter eventually, and that's kind of cool to think about, but it's absurdly negligible with the technology of today. Processors today are orders of magnitude slower than that.
  - smallnamespace 10y ago
    That's completely false. The speed of light today already constrains processor design (and by extension, on-CPU caches): http://arstechnica.com/science/2014/08/are-processors-pushing-up-against-the-limits-of-physics/ http://arstechnica.com/science/2014/08/are-processors-pushin... "Even if signals in the chip were moving at the speed of light, a chip running above 5GHz wouldn't be able to transmit information from one side of the chip to the other". Note that a light-nanosecond is about a foot, so I'm assuming this is talking about the propagation delay of electrons in silicon that need to go through gates, which I'm sure is much slower than light in a vacuum. To put this another way, you can view the scaling law as a hard upper bound on the speed of access to data; engineers can only approach that bound from below as technology improves. But given a certain level of technology, it's easier to make a faster L1 cache than an L2 cache, and that will hold even as we approach theoretical limits.
    - creshal 10y ago
deleted 10y ago
[deleted]

zeroer 10y ago

The author gets the definition of big-O completely backwards. Every single time the author says "Big-O" he means "little-o". Here are the definitions: https://cathyatseneca.gitbooks.io/data-structures-and-algorithms/content/analysis/notations.html https://cathyatseneca.gitbooks.io/data-structures-and-algori... Basically, big-O is a claim that your process is at least -this- fast. Small-o is a claim that your process can't be faster than -this-. He means the latter. > Still not convinced? Think I'm misunderstanding Big-O? Yea, I do.

jo909 10y ago
Please see https://en.wikipedia.org/wiki/Best,_worst_and_average_case https://en.wikipedia.org/wiki/Best,_worst_and_average_case Big-O is valid notation for _many aspects_ of an algorithm. The author applied it to a very practical one and explained what exactly he describes very well.
- reikonomusha 10y ago
  I think it's a massive and needless abuse of standard computer science terminology to re-define it as something completely different.
  - MrManatee 10y ago
    I'm not entirely sure what you are referring to. You might be referring to the fact that the author's definition of big-O doesn't say anything about constant factors or asymptotics. This makes the definition incorrect, or at least sloppy. But judging by usage, it seems that he actually knows and is using the standard definition. The error is just in that one sentence, and it doesn't affect the rest of the argument. You might also be objecting to the fact that he makes a distinction between time and instruction count, and is using big-O notation for both. I don't think there's anything nonstandard about making this distinction when it needs to be made. Take, for example, Karmarkar's algorithm: https://en.wikipedia.org/wiki/Karmarkar%27s_algorithm https://en.wikipedia.org/wiki/Karmarkar%27s_algorithm
- DanWaterworth 10y ago
  Re-read the article, bearing in mind that O(sqrt n) is a set that contains O(1).
  - angry_octet 10y ago
    Yes, but it isn't very helpful to think of it that way, we're not competing to find the weakest constraint.
- zeroer 10y ago
  The best/worst/average issue is orthogonal to the definition of what big-O means. The time it take an algorithm has best/worst/average cases, and each of these is a function and thus is a member of big-O classes. The definition of big-O has a completely standardized and unambiguous definition, and the author of the article somehow has a four-part blog post on big-O without knowing it.
smallnamespace 10y ago
You're right, but almost all colloquial usage of Big-O seems to be close to theta-O because people pick the tightest bound they can. That's why everyone writes that comparison sorts are O(n lg N), even though it's also technically O(exp N) as well.
- zeroer 10y ago
  Yea, I thought about that, but he doesn't mean theta, either. What he's giving is a physical impossibility proof -- you can't do memory access better than sqrt(N). When he gives a physical example of a machine of arbitrary size that accesses memory in sqrt(N) time, then we can talk about theta.
  - Animats 10y ago
    Well, cube root of N; you can stack memory. The speed of light limitation on distance to DRAM memory is real, but so far seems to affect mostly supercomputers. Are there any large server boards where speed of light lag is the limit on memory capacity?
    - zeroer 10y ago
      Read part two of the article. You can't stack memory indefinitely -- you'll get a black hole.
- perfectfire 10y ago
  > it's also technically O(exp N) as well. I wonder if this is what one interviewer was trying to get at when he asked me over and over again if a binary search was worst case O(log N). I just kept saying that if you took more than log N steps to perform a binary search then you by definition did not perform a binary search. He was off his rocker so I kind of doubt he was looking for the difference between little-o, theta, and big-O. It's good stuff to remember and might impress a more sane interviewer some day though.
rntz 10y ago
Your claims about what little-o and big-O mean don't match the explanation at https://cathyatseneca.gitbooks.io/data-structures-and-algorithms/content/analysis/notations.html https://cathyatseneca.gitbooks.io/data-structures-and-algori... That page says o(f) == O(f) and not Theta(f). When you say "small-o is a claim that your process can't be faster than -this-", that seems to match the definition of Omega(f). Did you mean that the author should have used big-Omega? As a side-note, I've always thought that {big-O,Theta,Omega,small-o} notation was very confusing. We should just have a notation for "the asymptotic equivalence class of a function", let's say A(f). Then to say f \in O(g), we say A(f) <= A(g). To say f \in Theta(g), we say A(f) = A(g). f \in o(g) becomes A(f) < A(g). And so forth. Instead of lots of new notation, we add a single function A and re-use notation for orderings which everyone already knows. (Of course, I'm omitting the definition of the ordering on these equivalence classes, so maybe there is some difficulty in defining that...)
- contravariant 10y ago
  >As a side-note, I've always thought that {big-O,Theta,Omega,small-o} notation was very confusing. We should just have a notation for "the asymptotic equivalence class of a function", let's say A(f). Then to say f \in O(g), we say A(f) <= A(g). To say f \in Theta(g), we say A(f) = A(g). f \in o(g) becomes A(f) < A(g). And so forth. Instead of lots of new notation, we add a single function A and re-use notation for orderings which everyone already knows. (Of course, I'm omitting the definition of the ordering on these equivalence classes, so maybe there is some difficulty in defining that...) Your A is pretty much equivalent to \Theta. Saying f \in \Theta(g) is equivalent to saying \Theta(f) = \Theta(g). Edit: as an aside O(f) = O(g) is also equivalent to f \in \Theta(g), and O(f) \subset O(g) is equivalent to f \in O(g).
  - rntz 10y ago
    For equality, yes, Theta works! But I care not just about equality but about comparison. In particular, it would be nice if the "natural" ordering on A(f) had the property that A(f) <= A(g) iff f is O(g) Theta(g) is a set, and the most natural ordering on sets is subsetting/inclusion. However, Theta(x) is not a subset of Theta(x^2), even though x is O(x^2)! So the natural ordering on sets doesn't do what I want. It might be possible to define an ordering on Theta-classes that does what I want, though. Edit: I just saw your comment about O. I think O might just work! So instead of remembering big-O, Theta, and Omega, I can just use O(f) <= O(g) for f is O(g) O(f) = O(g) for f is Theta(g) O(f) >= O(g) for f is Omega(g) Is that true? (I think small-o might be slightly more complicated, unfortunately. It has a more unusual definition: https://en.wikipedia.org/wiki/Big_O_notation#Little-o_notation https://en.wikipedia.org/wiki/Big_O_notation#Little-o_notati...)

smallnamespace 10y ago

> It does not make a difference how wacky or weird f is compared to g below t. It can contain all these crazy memory hierarchy artifacts, it could contain a short burst of exponential slowdown, it could contain anything. Yes, but if you continue reading the next post, the author is essentially arguing that the cache hierarchy extends indefinitely due to 1) the speed of light and 2) the amount of information that can fit within a light cone of a certain radius. In that case, cache hierarchy effects aren't 'weird things that happen below t', they represent the asymptotic behavior we can expect due to the laws of physics, no matter how far out to the right we go.

rosalinekarr 10y ago
Worrying about the speed of light in processor caching these days is like putting a spoiler on your cart and horse to reduce drag. It might matter eventually, and that's kind of cool to think about, but it's absurdly negligible with the technology of today. Processors today are orders of magnitude slower than that.
- smallnamespace 10y ago
  That's completely false. The speed of light today already constrains processor design (and by extension, on-CPU caches): http://arstechnica.com/science/2014/08/are-processors-pushing-up-against-the-limits-of-physics/ http://arstechnica.com/science/2014/08/are-processors-pushin... "Even if signals in the chip were moving at the speed of light, a chip running above 5GHz wouldn't be able to transmit information from one side of the chip to the other". Note that a light-nanosecond is about a foot, so I'm assuming this is talking about the propagation delay of electrons in silicon that need to go through gates, which I'm sure is much slower than light in a vacuum. To put this another way, you can view the scaling law as a hard upper bound on the speed of access to data; engineers can only approach that bound from below as technology improves. But given a certain level of technology, it's easier to make a faster L1 cache than an L2 cache, and that will hold even as we approach theoretical limits.
  - creshal 10y ago

deleted 10y ago

[deleted]