3 ms·
An order of magnitude is not necessarily a factor of 10. Otherwise we would always just say, "factor of 10" which has fewer syllables. The difference between O(
by ludston 3y ago
An order of magnitude is not necessarily a factor of 10. Otherwise we would always just say, "factor of 10" which has fewer syllables. The difference between O(logn) to O(1) is often referred to as an order of magnitude. As is O(logn) to O(n).
- vincent-manis 3y agoI taught algorithms and data structures a lot. We never referred to differences in complexity as orders of magnitude, though you might say that Algorithm A's running time differs from B's running time on the same data by an order of magnitude. Also, the point about logarithmic time is that it grows much more slowly than even linear time: log2(128) is only 7, and log2(1024) is only 10.
- thaumasiotes 3y ago> The difference between O(logn) to O(1) is often referred to as an order of magnitude. As is O(logn) to O(n). That isn't good usage, but there was enough context in your comment to guess that that was what you meant. The main problem I was pointing out is that the difference between O(log n) and O(1) is much, much, much, much, much, much smaller than the difference between O(log n) and O(n), so it doesn't make sense to describe those two differences the same way.