5 ms·
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,
by 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 agoThe important pre knowledge is that every polynomial is dominated by its largest exponential term (for x to infty).
- pmiller2 6y agoIt'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 agoLargest 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 agoOne 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 agoSure 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 agoOne 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 agoAh, 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 agoUnless 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 agoprobably you meant monotonicity
- 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 agoSure, 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.