3 ms·
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?
by 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 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