4 ms·
O(n^k) where 0 < k < 1
by kuprel 4y ago
O(n^k) where 0 < k < 1
- aaaaaaaaaaab 4y agoMore like o(n).
- quantum_mcts 4y agoWould O(ln n) be "sublinear", though?
- deleted 4y ago[deleted]
- thaumasiotes 4y agoOf course. kuprel already said so.
- sterlind 4y agoI'm bad at math, but this is because d/dx ln(x) = x^-1, while d/dx x^k = kx^(-1+k), so as long as k > 0 the derivative of the latter is larger, right?
- selimthegrim 4y agoWell sure but you can also just graph them or compare Taylor series (in radius of convergence, appropriate cut, etc)
- thaumasiotes 4y agoWell, the question here was just "is ln(x) sublinear or not?". You can answer that question with much less work: the second derivative is always negative, so the function must be sublinear. Any function that grows linearly must have a second derivative of zero.