5 ms·

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 var

by 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.
      - aborsy 6y ago
        |g(x)|<M|f(x)| does not imply |g’(x)|<=C|f’(x)|.
        pmiller2 6y ago
        Sure it does, for all functions f and g that we actually care about in the CS context for big-O. Hint: what if f and g are smooth?
        aborsy 6y ago
        One function could be below another and have arbitrarily derivative. Even if they are both smooth: f(x)=sin(e^x) and g(x)=1.
        pmiller2 6y ago
        Ah, yes, right. Smoothness alone doesn't do it. Nonetheless, I still maintain that the property holds for all functions that we actually care about when doing analysis of algorithms. In particular, it certainly holds for sums and products of n! e^n, n log n, n, log n, and 1, which covers probably 99.9% of everything I've ever seen inside an O().
        gvx 6y ago
        Unless I'm mistaken, |g(x)|<M|f(x)| does not hold for those, since sin(e^x) has an infinite number of zeroes.
- sabas123 6y ago
  > But, the amount of prerequisite knowledge one needs to understand this is very, very little, and would easily fit in a digestible web page I'm really not sure on this one. This is easy if you have an idea of: 1. how you can graph things (runtime vs input size) 2. do the same but stretching the function to infinity 3. compare this to some term (which isn't as tangible compared to most algorithms imo), And this is only for the intuition part. For people that got into programming by doing some UI stuff, I can definitely can see why _a subset of people_ struggle with this.
  - pmiller2 6y ago
    Sure, a subset may struggle. That's beside the point. I'm most interested in giving people who, as I mentioned, have a basic fluency with functions of the real numbers the answer to why you drop constant multiples and everything but the most significant term. If I wanted to make sure everybody understood (which isn't even theoretically possible), I'd have to include the better part of a semester-long course in my explanation, and that defeats the purpose of having everything in a digestible format.
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.

by 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.
    - aborsy 6y ago
      |g(x)|<M|f(x)| does not imply |g’(x)|<=C|f’(x)|.
      - pmiller2 6y ago
        Sure it does, for all functions f and g that we actually care about in the CS context for big-O. Hint: what if f and g are smooth?
        aborsy 6y ago
        One function could be below another and have arbitrarily derivative. Even if they are both smooth: f(x)=sin(e^x) and g(x)=1.
        pmiller2 6y ago
        Ah, yes, right. Smoothness alone doesn't do it. Nonetheless, I still maintain that the property holds for all functions that we actually care about when doing analysis of algorithms. In particular, it certainly holds for sums and products of n! e^n, n log n, n, log n, and 1, which covers probably 99.9% of everything I've ever seen inside an O().
        gvx 6y ago
        Unless I'm mistaken, |g(x)|<M|f(x)| does not hold for those, since sin(e^x) has an infinite number of zeroes.
sabas123 6y ago
> But, the amount of prerequisite knowledge one needs to understand this is very, very little, and would easily fit in a digestible web page I'm really not sure on this one. This is easy if you have an idea of: 1. how you can graph things (runtime vs input size) 2. do the same but stretching the function to infinity 3. compare this to some term (which isn't as tangible compared to most algorithms imo), And this is only for the intuition part. For people that got into programming by doing some UI stuff, I can definitely can see why _a subset of people_ struggle with this.
- pmiller2 6y ago
  Sure, a subset may struggle. That's beside the point. I'm most interested in giving people who, as I mentioned, have a basic fluency with functions of the real numbers the answer to why you drop constant multiples and everything but the most significant term. If I wanted to make sure everybody understood (which isn't even theoretically possible), I'd have to include the better part of a semester-long course in my explanation, and that defeats the purpose of having everything in a digestible format.

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.