Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

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



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.


|g(x)|<M|f(x)| does not imply |g’(x)|<=C|f’(x)|.


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?


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.


Unless I'm mistaken, |g(x)|<M|f(x)| does not hold for those, since sin(e^x) has an infinite number of zeroes.


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().


probably you meant monotonicity




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: