3 ms·

But what do you do once something becomes very slow? Creating a database index, for example, is a beautiful example of O(log n) :)

Joeboy 13y ago
But in that case, knowing Big-O notation is a retrospective explanation of something any quarter-decent developer knows already. You don't need to know Big-O in order to know how/when to create a database index.
- greenyoda 13y ago
  It doesn't have to be retrospective. A knowledge of computational complexity can be used to make predictions about the performance of a system (even one you haven't implemented yet). What if your manager asked you for an estimate of how long it would take to load a million new records into the database and index them? It would be nice to know whether you'd have to take the system down for an hour or for a day or for a week. What if the performance of your code was slow and you wanted to know whether it could possibly be improved, and by how much. Knowing the theoretical limitations of the algorithm you were running (e.g., sorting takes at least O(n log n)) could tell you what kind of optimizations you could reasonably expect to make or whether you needed to invest in faster hardware.
  - Joeboy 13y ago
    > What if your manager asked you for an estimate of how long it would take to load a million new records into the database and index them? It would be nice to know whether you'd have to take the system down for an hour or for a day or for a week. I don't think I really buy this as a practical use case. Unless I was running on system I understood very well (eg. an embedded platform) I don't think I'd really trust estimates calculated using Big-O to be reliable on atypical workloads. I'd pretty much expect unforeseen caches / optimizations / swapping to disk to confound my estimates somehow. If at all possible I'd test it. If testing it takes too long to be practical then there's a serious problem with the system. I can see cases where testing is impossible for good, practical reasons, just not enough of them to justify the obsession with Big-O.
greenyoda 13y ago
Wouldn't inserting a single record in the index be O(log n) (if n is the number of records in the index), and creating the entire index be O(n log n)?

Joeboy 13y ago

But in that case, knowing Big-O notation is a retrospective explanation of something any quarter-decent developer knows already. You don't need to know Big-O in order to know how/when to create a database index.

greenyoda 13y ago
It doesn't have to be retrospective. A knowledge of computational complexity can be used to make predictions about the performance of a system (even one you haven't implemented yet). What if your manager asked you for an estimate of how long it would take to load a million new records into the database and index them? It would be nice to know whether you'd have to take the system down for an hour or for a day or for a week. What if the performance of your code was slow and you wanted to know whether it could possibly be improved, and by how much. Knowing the theoretical limitations of the algorithm you were running (e.g., sorting takes at least O(n log n)) could tell you what kind of optimizations you could reasonably expect to make or whether you needed to invest in faster hardware.
- Joeboy 13y ago
  > What if your manager asked you for an estimate of how long it would take to load a million new records into the database and index them? It would be nice to know whether you'd have to take the system down for an hour or for a day or for a week. I don't think I really buy this as a practical use case. Unless I was running on system I understood very well (eg. an embedded platform) I don't think I'd really trust estimates calculated using Big-O to be reliable on atypical workloads. I'd pretty much expect unforeseen caches / optimizations / swapping to disk to confound my estimates somehow. If at all possible I'd test it. If testing it takes too long to be practical then there's a serious problem with the system. I can see cases where testing is impossible for good, practical reasons, just not enough of them to justify the obsession with Big-O.

greenyoda 13y ago

Wouldn't inserting a single record in the index be O(log n) (if n is the number of records in the index), and creating the entire index be O(n log n)?