6 ms·

Every one of these "Big-O explainers" says pretty much the same thing: count (or bound) the number of steps, then take the most significant term, and drop the c

Every one of these "Big-O explainers" says pretty much the same thing: count (or bound) the number of steps, then take the most significant term, and drop the constant associated with it. None of them explain why you take the most significant term or drop constant factors. I get why that is. You need the mathematical definition to demonstrate why that is, and most "Big-O explainers" don't want to assume any significant amount of mathematical background. But, that definition isn't that hard. It's simply: f(x) is O(g(x)) iff there exists a positive number M and an x_0 such that for all x > x_0, |f(x)| <= Mg(x). And, if you're in an analysis of algorithms context, it's even easier, because you typically don't have to worry about this absolute value business. Well, that M is essentially the reason you get to drop constant multiples of f(x). And, you drop the least significant terms of f(x) because g(x) dominates them, i.e. lim_{x -> \infty} g(x)/f(x) = 0. (No need to prove this, because this is what makes the "less significant" terms less significant.) I would also like to add that the equals sign in f(x) = O(g(x)) is one of the most useful abuses of notation that I know of, but it can be misleading. It doesn't behave at all like a real equality because it's not symmetric, but it is transitive and reflexive. It actually acts more like set membership than equality.

casion 6y ago
You say it isn't hard, but I have 2 graduate degrees and didn't understand your explanation at all. "Hard" is relative to prerequisite knowledge, which can vary significantly.
- roywiggins 6y ago
  The short version is that the fastest-growing term dominates all the others and for large xs the smaller terms round down to zero. Since big-O notation is about how the complexity grows for large inputs, you can assume the input is arbitrarily large, and you'll notice that the complexity is completely determined by the fastest-growing term. You drop the constant because it doesn't alter how the complexity grows as the input increases.
- pmiller2 6y ago
  Of course "hard" is relative. Because I was writing a HN post and not a "Big-O explainer," I didn't provide you with any of that prerequisite knowledge. But, the amount of prerequisite knowledge one needs to understand this is very, very little, and would easily fit in a digestible web page, provided you have some basic fluency with functions of the real numbers. And, I think that's a reasonable level of prerequisite to assume for anyone who wants to be throwing around terms like "Big-O." If it's not too intrusive, may I ask what your graduate degrees are?
  - andi999 6y ago
    The important pre knowledge is that every polynomial is dominated by its largest exponential term (for x to infty).
    - pmiller2 6y ago
      It's a little more than that. You need to account for the fact that n log n dominates n, but not n^2, as well. That's not hard, but you should spell it out. This discussion is making me think that a good way to write a "Big-O explainer" would be sort of like a progressive web app, i.e. "here's the explanation with the highest level of mathematical sophistication. Click here to get some of the prerequisite knowledge." Then, the user just keeps clicking "break it down more" until either they get it or they reach the most detailed explanation.
    - mhh__ 6y ago
      Largest exponential? That should be monomial, right? Anyway you can show that on the spot if you think about what the derivative of that monomial looks like
      - pmiller2 6y ago
        One easy way to show that more generally is that if f and g are differentiable, f(x) dominates g(x) iff f'(x) dominates g'(x), by L'Hopital's rule. Details left as an exercise for the reader.
- andi999 6y ago
  Had such students as well. If I ask anything they said, oh I learned that as undergrad (implying that it is too long ago to remember). I am sad about such a waste.
  - casion 6y ago
    Not sure what this is supposed to mean. Apparently this requires calc knowledge, which I was never required to take!
- mhh__ 6y ago
  Admittedly I am studying theoretical physics so I am supposed to be able to, but it made sense to me?
  - pmiller2 6y ago
    Excellent! The level I was shooting for with my brief explanation was that someone who understood limits at a calc 1 level should be able to get it with a little thinking. I do wonder, though: did you know those things before you read my comment?
    - mhh__ 6y ago
      I did. For some scale of what I get up to I'm currently banging my head against various differential geometry textbooks. Ultimately you're limited in not having graphs, which always limits the intuitiveness of any calculus-explainers.
      - pmiller2 6y ago
        Cool. Sounds like you're in grad school right now, yeah? I know differential geometry is not exactly the same as differential topology, but I remember taking differential topology in grad school. I was always amused that we never actually evaluated any integrals that didn't come out to a very simple number (generally 0). If I were writing this as a web page, though, I would definitely include a few graphs to explain the calculus concepts. The amount of calculus you need here is pretty intuitive once you draw a couple of pictures.
        mhh__ 6y ago
        I'm actually in my second year of university but I started learning physics "properly" at 14 so I had a head start.
- kergonath 6y ago
  This bit: >> f(x) is O(g(x)) iff there exists a positive number M and an x_0 such that for all x > x_0, |f(x)| <= Mg(x). is fairly similar to the so-called epsilon-delta definition of limits of functions. This way of reasoning is quite common. I know I bumped into it quite a lot: I learnt it in high school, even though I really understood it a couple of years later (I did a MSc in Physics). So the explanation above makes sense even if I never saw this exact formulation. Now I appreciate that not everyone is a Physics graduate, but I’d expect this to be understandable for people with degrees in applied Maths, Physics, or some related engineering discipline.
- kaba0 6y ago
  A function f(n) is O(g(n)) if the graph of f will be underneath the graph of g(n) for a big enough n. (If we want to be more correct, then I would have to add that if there exists a positive number c, and cg should be above the graph of f) So f(n):=3n+28 will be O(n^2), because choosing c as 3, for every n greater than or equal 4, 3n^2 will be greater than f(n). It would help if I could draw some graphs, but hopefully it helps.
jakear 6y ago
It acts exactly like set membership, because that’s what it is.
uh_uh 6y ago
> And, you drop the least significant terms of f(x) because g(x) dominates them, i.e. lim_{x -> \infty} g(x)/f(x) = 0. If g(x) dominates all the terms in f(x), then wouldn't lim_{x -> \infty} g(x)/f(x) go to infinity?
edflsafoiewq 6y ago
In most practical cases f=O(g) is the same as saying f/g is bounded.
Al-Khwarizmi 6y ago
I'd say that the = is one of the most annoying abuses of notation that I know of, if not the most. Apart from not symmetric, which is a problem in its own right, for small o and small omega it's not even reflexive, which does not prevent the = users from using it also for those. Which amounts to using an equals sign to highlight how two functions differ. And what do people gain with that? It's not as if a set membership symbol, which works just fine because big O, small o, the omegas and their ilk define sets of functions, doesn't work just fine and take the same space without being confusing.
- edflsafoiewq 6y ago
  The notation is from math; the point of it is that you can manipulate it like a normal expression, but it's "anonymous"; o(1) means some function that goes to zero, but we don't bother with a name, just recording the asymptotic behavior. For example, f'(x) = lim (f(x+h)-f(x))/h can be rewritten with an error term f'(x) = (f(x+h)-f(x))/h + o(1), and then you can manipulate it more freely, say like f(x+h) = f(x) + hf'(x) + o(h). There's no need to drag out a bunch of useless names, each qualified by a set membership, to do this. I mean e(h) in o(1), e2(h) := h e(h) in o(h), etc. The failure of "reflexivity", eg O(f) = O(f), is because the anonymity hides whether the two O(f)s are referring to the same function (ie. exactly what a name would tell us).
Tade0 6y ago
I understood your definition (all in all I had calculus 101) but to me it only describes why that is, it doesn't explain it. Most Big-O explainers don't assume a mathematical background because to non-mathematicians parsing your definition feels like being told you're in a hot air balloon. They see the what, but they don't understand the why.
otabdeveloper4 6y ago
> f(x) is O(g(x)) iff there exists a positive number M and an x_0 such that for all x > x_0, |f(x)| <= Mg(x). Correct. Corollary: x is O(x^2), for example.

casion 6y ago

You say it isn't hard, but I have 2 graduate degrees and didn't understand your explanation at all. "Hard" is relative to prerequisite knowledge, which can vary significantly.

roywiggins 6y ago
The short version is that the fastest-growing term dominates all the others and for large xs the smaller terms round down to zero. Since big-O notation is about how the complexity grows for large inputs, you can assume the input is arbitrarily large, and you'll notice that the complexity is completely determined by the fastest-growing term. You drop the constant because it doesn't alter how the complexity grows as the input increases.
pmiller2 6y ago
Of course "hard" is relative. Because I was writing a HN post and not a "Big-O explainer," I didn't provide you with any of that prerequisite knowledge. But, the amount of prerequisite knowledge one needs to understand this is very, very little, and would easily fit in a digestible web page, provided you have some basic fluency with functions of the real numbers. And, I think that's a reasonable level of prerequisite to assume for anyone who wants to be throwing around terms like "Big-O." If it's not too intrusive, may I ask what your graduate degrees are?
- andi999 6y ago
  The important pre knowledge is that every polynomial is dominated by its largest exponential term (for x to infty).
  - pmiller2 6y ago
    It's a little more than that. You need to account for the fact that n log n dominates n, but not n^2, as well. That's not hard, but you should spell it out. This discussion is making me think that a good way to write a "Big-O explainer" would be sort of like a progressive web app, i.e. "here's the explanation with the highest level of mathematical sophistication. Click here to get some of the prerequisite knowledge." Then, the user just keeps clicking "break it down more" until either they get it or they reach the most detailed explanation.
  - mhh__ 6y ago
    Largest exponential? That should be monomial, right? Anyway you can show that on the spot if you think about what the derivative of that monomial looks like
    - pmiller2 6y ago
      One easy way to show that more generally is that if f and g are differentiable, f(x) dominates g(x) iff f'(x) dominates g'(x), by L'Hopital's rule. Details left as an exercise for the reader.
andi999 6y ago
Had such students as well. If I ask anything they said, oh I learned that as undergrad (implying that it is too long ago to remember). I am sad about such a waste.
- casion 6y ago
  Not sure what this is supposed to mean. Apparently this requires calc knowledge, which I was never required to take!
mhh__ 6y ago
Admittedly I am studying theoretical physics so I am supposed to be able to, but it made sense to me?
- pmiller2 6y ago
  Excellent! The level I was shooting for with my brief explanation was that someone who understood limits at a calc 1 level should be able to get it with a little thinking. I do wonder, though: did you know those things before you read my comment?
  - mhh__ 6y ago
    I did. For some scale of what I get up to I'm currently banging my head against various differential geometry textbooks. Ultimately you're limited in not having graphs, which always limits the intuitiveness of any calculus-explainers.
    - pmiller2 6y ago
      Cool. Sounds like you're in grad school right now, yeah? I know differential geometry is not exactly the same as differential topology, but I remember taking differential topology in grad school. I was always amused that we never actually evaluated any integrals that didn't come out to a very simple number (generally 0). If I were writing this as a web page, though, I would definitely include a few graphs to explain the calculus concepts. The amount of calculus you need here is pretty intuitive once you draw a couple of pictures.
      - mhh__ 6y ago
        I'm actually in my second year of university but I started learning physics "properly" at 14 so I had a head start.
kergonath 6y ago
This bit: >> f(x) is O(g(x)) iff there exists a positive number M and an x_0 such that for all x > x_0, |f(x)| <= Mg(x). is fairly similar to the so-called epsilon-delta definition of limits of functions. This way of reasoning is quite common. I know I bumped into it quite a lot: I learnt it in high school, even though I really understood it a couple of years later (I did a MSc in Physics). So the explanation above makes sense even if I never saw this exact formulation. Now I appreciate that not everyone is a Physics graduate, but I’d expect this to be understandable for people with degrees in applied Maths, Physics, or some related engineering discipline.
kaba0 6y ago
A function f(n) is O(g(n)) if the graph of f will be underneath the graph of g(n) for a big enough n. (If we want to be more correct, then I would have to add that if there exists a positive number c, and cg should be above the graph of f) So f(n):=3n+28 will be O(n^2), because choosing c as 3, for every n greater than or equal 4, 3n^2 will be greater than f(n). It would help if I could draw some graphs, but hopefully it helps.

jakear 6y ago

It acts exactly like set membership, because that’s what it is.

uh_uh 6y ago

> And, you drop the least significant terms of f(x) because g(x) dominates them, i.e. lim_{x -> \infty} g(x)/f(x) = 0. If g(x) dominates all the terms in f(x), then wouldn't lim_{x -> \infty} g(x)/f(x) go to infinity?

edflsafoiewq 6y ago

In most practical cases f=O(g) is the same as saying f/g is bounded.

Al-Khwarizmi 6y ago

I'd say that the = is one of the most annoying abuses of notation that I know of, if not the most. Apart from not symmetric, which is a problem in its own right, for small o and small omega it's not even reflexive, which does not prevent the = users from using it also for those. Which amounts to using an equals sign to highlight how two functions differ. And what do people gain with that? It's not as if a set membership symbol, which works just fine because big O, small o, the omegas and their ilk define sets of functions, doesn't work just fine and take the same space without being confusing.

edflsafoiewq 6y ago
The notation is from math; the point of it is that you can manipulate it like a normal expression, but it's "anonymous"; o(1) means some function that goes to zero, but we don't bother with a name, just recording the asymptotic behavior. For example, f'(x) = lim (f(x+h)-f(x))/h can be rewritten with an error term f'(x) = (f(x+h)-f(x))/h + o(1), and then you can manipulate it more freely, say like f(x+h) = f(x) + hf'(x) + o(h). There's no need to drag out a bunch of useless names, each qualified by a set membership, to do this. I mean e(h) in o(1), e2(h) := h e(h) in o(h), etc. The failure of "reflexivity", eg O(f) = O(f), is because the anonymity hides whether the two O(f)s are referring to the same function (ie. exactly what a name would tell us).

Tade0 6y ago

I understood your definition (all in all I had calculus 101) but to me it only describes why that is, it doesn't explain it. Most Big-O explainers don't assume a mathematical background because to non-mathematicians parsing your definition feels like being told you're in a hot air balloon. They see the what, but they don't understand the why.

otabdeveloper4 6y ago

> f(x) is O(g(x)) iff there exists a positive number M and an x_0 such that for all x > x_0, |f(x)| <= Mg(x). Correct. Corollary: x is O(x^2), for example.