3 ms·

But the VAST majority of the programming work out there does not require any Big-O analysis. Your point is simultaneously valid and irrelevant. The vast m

But the VAST majority of the programming work out there does not require any Big-O analysis. Your point is simultaneously valid and irrelevant. The vast majority of programming doesn't involve any Big-O analysis. But if you can't do Big-O analysis, there are problems where you will be stuck. Your code will be running slowly and you won't know why, and all the micro-optimizations in the world can't make a O(n^2) algorithm run faster than an O(n) algorithm on even a moderately large data set. To make an analogy with driving: the vast majority of driving doesn't involve parallel parking. But you still need to know parallel parking to pass a driving test.

nrb 11y ago
You do not need to know parallel parking to pass a driving test, in Illinois and probably many other states.
whatshisface 11y ago
You don't need to know how to prove a big-O to optimize an algorithm. Anyone who can think about what their code is doing will have at least some sense of how much it is doing. Honestly, I don't think calculating the O(f(n)) is ever worth it outside of academia. Intuition is only slightly worse, and it is just so much time-cheaper.
- quanticle 11y ago
  Honestly, I don't think calculating the O(f(n)) is ever worth it outside of academia. Intuition is only slightly worse, and it is just so much time-cheaper. Sure. I've never been asked for a formal mathematical proof of the Big-O complexity of my algorithms in an interview. And, as an interviewer, I've never asked. Intuition is exactly what interviews are looking for. If an algorithm has a nested for loop, and the inner loop is traversing the full data set, you should be able to say, "Oh, yeah, that looks like O(n^2) time complexity." If an algorithm is storing every element of a data-set in memory, you should be able to say, "That's O(n) space complexity." Big-O notation, in practice, is a handy shorthand for talking about various classes of algorithms, and ranking them in order of how much time/space they take.
vonmoltke 11y ago
> But if you can't do Big-O analysis, there are problems where you will be stuck. Your code will be running slowly and you won't know why, and all the micro-optimizations in the world can't make a O(n^2) algorithm run faster than an O(n) algorithm on even a moderately large data set. This may be a result of the domains I have worked in, but I have never encountered a situation where I could change the order-of-growth on an algorithm. In fact, most algorithms I have worked with have been defined by non-computational performance. I don't know formal complexity analysis, and personally think the resolution of Big-O is far too coarse for practical analysis anyway. I can still look at any piece of code and give you approximate polynomials for its runtime, memory requirements, and other computational features.
forgetsusername 11y ago
>To make an analogy with driving The whole point of the argument is the difference between what's on the test and reality, though. And simply "being on the test" doesn't make it valuable. Needing to parallel park on the driving test has little relation to you being a good driver. In reality, your actual ability to park is hardly relevant, because you could avoid those parking spaces, or even half-ass it by driving in forward, or whatever.
Alex3917 11y ago
> Your code will be running slowly and you won't know why Ever hear the expression "tools, not rules"? Using big-O analysis while coding is almost the textbook definition of what makes someone a bad developer. That's of course not true if you're developing some foundational tool meant for other developers like Redis or whatever, but for the average developer doing complexity analysis at work is probably a red flag that they're prematurely optimizing their code, using company time to work on a side project, or otherwise doing something that's not contributing to the success of the business.
ken47 11y ago
But if you can't do Big-O analysis, there are problems where you will be stuck. Your code will be running slowly and you won't know why, and all the micro-optimizations in the world can't make a O(n^2) algorithm run faster than an O(n) algorithm on even a moderately large data set. That's actually incorrect. Not knowing Big O does not prove that you do not know how to optimize an algorithm. However, it does mean that you don't speak the common language of computer science, that would allow you to easily communicate the effect of your optimizations to other programmers.

nrb 11y ago

You do not need to know parallel parking to pass a driving test, in Illinois and probably many other states.

whatshisface 11y ago

You don't need to know how to prove a big-O to optimize an algorithm. Anyone who can think about what their code is doing will have at least some sense of how much it is doing. Honestly, I don't think calculating the O(f(n)) is ever worth it outside of academia. Intuition is only slightly worse, and it is just so much time-cheaper.

quanticle 11y ago
Honestly, I don't think calculating the O(f(n)) is ever worth it outside of academia. Intuition is only slightly worse, and it is just so much time-cheaper. Sure. I've never been asked for a formal mathematical proof of the Big-O complexity of my algorithms in an interview. And, as an interviewer, I've never asked. Intuition is exactly what interviews are looking for. If an algorithm has a nested for loop, and the inner loop is traversing the full data set, you should be able to say, "Oh, yeah, that looks like O(n^2) time complexity." If an algorithm is storing every element of a data-set in memory, you should be able to say, "That's O(n) space complexity." Big-O notation, in practice, is a handy shorthand for talking about various classes of algorithms, and ranking them in order of how much time/space they take.

vonmoltke 11y ago

> But if you can't do Big-O analysis, there are problems where you will be stuck. Your code will be running slowly and you won't know why, and all the micro-optimizations in the world can't make a O(n^2) algorithm run faster than an O(n) algorithm on even a moderately large data set. This may be a result of the domains I have worked in, but I have never encountered a situation where I could change the order-of-growth on an algorithm. In fact, most algorithms I have worked with have been defined by non-computational performance. I don't know formal complexity analysis, and personally think the resolution of Big-O is far too coarse for practical analysis anyway. I can still look at any piece of code and give you approximate polynomials for its runtime, memory requirements, and other computational features.

forgetsusername 11y ago

>To make an analogy with driving The whole point of the argument is the difference between what's on the test and reality, though. And simply "being on the test" doesn't make it valuable. Needing to parallel park on the driving test has little relation to you being a good driver. In reality, your actual ability to park is hardly relevant, because you could avoid those parking spaces, or even half-ass it by driving in forward, or whatever.

Alex3917 11y ago

> Your code will be running slowly and you won't know why Ever hear the expression "tools, not rules"? Using big-O analysis while coding is almost the textbook definition of what makes someone a bad developer. That's of course not true if you're developing some foundational tool meant for other developers like Redis or whatever, but for the average developer doing complexity analysis at work is probably a red flag that they're prematurely optimizing their code, using company time to work on a side project, or otherwise doing something that's not contributing to the success of the business.

ken47 11y ago

But if you can't do Big-O analysis, there are problems where you will be stuck. Your code will be running slowly and you won't know why, and all the micro-optimizations in the world can't make a O(n^2) algorithm run faster than an O(n) algorithm on even a moderately large data set. That's actually incorrect. Not knowing Big O does not prove that you do not know how to optimize an algorithm. However, it does mean that you don't speak the common language of computer science, that would allow you to easily communicate the effect of your optimizations to other programmers.