4 ms·

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.
      - andi999 6y ago
        probably you meant monotonicity

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.
    - andi999 6y ago
      probably you meant monotonicity