5 ms·

Most of the time, if you're thinking about big-O, you're practicing pre-mature optimization. Just write the code using your language's sort() function. If by pr

Most of the time, if you're thinking about big-O, you're practicing pre-mature optimization. Just write the code using your language's sort() function. If by profiling you determine the call to sort() is a bottleneck, then AND ONLY THEN should you consider analyzing the big-o implications of the different sort algorithms.

lucian1900 14y ago
However, it is often important to keep in mind how a particular functionality will scale. Complexity is an excellent way to gauge that.
thirsteh 14y ago
I strongly disagree. Good developers have a sort of Big-O intuition at the back of their minds that automatically tells them that the nested for loop they're writing to find a string in an array, and using an array in the first place, might not be the right approach. Big-O applies to a hell of a lot more than just sorting algorithms, and no language lets you ignore the varying degrees of complexity that come from the choices you make. Good developers consider Big-O implications all the time, without explicitly thinking about it. They don't ignore it.
- meaty 14y ago
  I think this is the most elegant set of reasons. We actually test incoming staff to make sure they are aware of complexity by giving them programming tasks that they can hang themselves with by using the wrong data structures or algorithms.
dinkumthinkum 14y ago
No, that's not true. That may be true if your whole world is making CRUD apps but there is a whole world out there. People use the phrase "pre-mature optimization" as a crunch to not understand how computers work.
- paulgb 14y ago
  Exactly. If you're building a todo list maybe you can ignore complexity, but if you're working on a data pipeline and you ignore (at least an intuitive sense of) O-notation, it will bit you in the ass.
- 10098 14y ago
  This. I can't comprehend it when people use sort() to find the min/max element instead of a linear scan. And yes, I've seen it happen.
  - lucian1900 14y ago
    That's not a particularly bad example, only O(n) vs O(n logn).
- philhippus 14y ago
  So Donald Knuth was trying to get out of understanding computers, got it.
  - Derander 14y ago
    The actual quote reads: "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil." O(n) vs O(n^2) is not a small efficiency for non-trivial data sets. This is the point that was being made. Many people forget that the quote hinges on the word "small" and then use that as an excuse to disengage their brain when it comes to basic things.
  - dinkumthinkum 14y ago
    That's an extremely simplistic, sort of childish response. No one besmirches Donald Knuth. Taking a quote, out of context really, and using it everywhere as some sort of justification, nay, an unthinking reflex, is, indeed, using it as a crutch.
- slurgfest 14y ago
  People also use the phrase "premature optimization" to make a perfectly accurate observation about eager, costly optimizations which may be obviated by changes or have no meaningful relationship to any business need. Is there really any good reason not to focus optimization on areas it will make a difference, and guide it with actual profiling results?
martinced 14y ago
Writing correct code is about chosing correct data structures for the problem at hand as much as "coding". And chosing the correct data structure comes down to understanding the performances (using Big-O / best-worst-average or Analytic Combinatorics) of the operations you're going to perform and the algorithms you're going to use on these data structures. It really sucks to have to refactor a codebase because some coder thoughts that lists would have been great there when actually a bi-dir map was what was needed (and vice-versa).
- mjcohen 14y ago
  Algorithms + Data Structures -> Programs.
guard-of-terra 14y ago
It's not only sort. Any loop with function calls inside can be a source of runaway complexity.
jiggy2011 14y ago
It seems impossible to talk about Big O without comparing sorting algorithms. I guess this is because every college course on the planet compares sorting algorithms for half the semester. If you have code which does a database query, parses some result and then generates HTML based on that; this is an algorithm. If your Javascript walks the DOM finding elements then that is an algorithm. These things all have associated computational costs which will scale depending on the input size.

lucian1900 14y ago

However, it is often important to keep in mind how a particular functionality will scale. Complexity is an excellent way to gauge that.

thirsteh 14y ago

I strongly disagree. Good developers have a sort of Big-O intuition at the back of their minds that automatically tells them that the nested for loop they're writing to find a string in an array, and using an array in the first place, might not be the right approach. Big-O applies to a hell of a lot more than just sorting algorithms, and no language lets you ignore the varying degrees of complexity that come from the choices you make. Good developers consider Big-O implications all the time, without explicitly thinking about it. They don't ignore it.

meaty 14y ago
I think this is the most elegant set of reasons. We actually test incoming staff to make sure they are aware of complexity by giving them programming tasks that they can hang themselves with by using the wrong data structures or algorithms.

dinkumthinkum 14y ago

No, that's not true. That may be true if your whole world is making CRUD apps but there is a whole world out there. People use the phrase "pre-mature optimization" as a crunch to not understand how computers work.

paulgb 14y ago
Exactly. If you're building a todo list maybe you can ignore complexity, but if you're working on a data pipeline and you ignore (at least an intuitive sense of) O-notation, it will bit you in the ass.
10098 14y ago
This. I can't comprehend it when people use sort() to find the min/max element instead of a linear scan. And yes, I've seen it happen.
- lucian1900 14y ago
  That's not a particularly bad example, only O(n) vs O(n logn).
philhippus 14y ago
So Donald Knuth was trying to get out of understanding computers, got it.
- Derander 14y ago
  The actual quote reads: "We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil." O(n) vs O(n^2) is not a small efficiency for non-trivial data sets. This is the point that was being made. Many people forget that the quote hinges on the word "small" and then use that as an excuse to disengage their brain when it comes to basic things.
- dinkumthinkum 14y ago
  That's an extremely simplistic, sort of childish response. No one besmirches Donald Knuth. Taking a quote, out of context really, and using it everywhere as some sort of justification, nay, an unthinking reflex, is, indeed, using it as a crutch.
slurgfest 14y ago
People also use the phrase "premature optimization" to make a perfectly accurate observation about eager, costly optimizations which may be obviated by changes or have no meaningful relationship to any business need. Is there really any good reason not to focus optimization on areas it will make a difference, and guide it with actual profiling results?

martinced 14y ago

Writing correct code is about chosing correct data structures for the problem at hand as much as "coding". And chosing the correct data structure comes down to understanding the performances (using Big-O / best-worst-average or Analytic Combinatorics) of the operations you're going to perform and the algorithms you're going to use on these data structures. It really sucks to have to refactor a codebase because some coder thoughts that lists would have been great there when actually a bi-dir map was what was needed (and vice-versa).

mjcohen 14y ago
Algorithms + Data Structures -> Programs.

guard-of-terra 14y ago

It's not only sort. Any loop with function calls inside can be a source of runaway complexity.

jiggy2011 14y ago

It seems impossible to talk about Big O without comparing sorting algorithms. I guess this is because every college course on the planet compares sorting algorithms for half the semester. If you have code which does a database query, parses some result and then generates HTML based on that; this is an algorithm. If your Javascript walks the DOM finding elements then that is an algorithm. These things all have associated computational costs which will scale depending on the input size.