Hacker Newsnew | comments | show | ask | jobs | submit login

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



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)?

-----


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.

-----


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.

-----


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

-----




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | DMCA | Apply to YC | Contact

Search: