3 ms·

Someone convince me that Big-O notation is useful anywhere outside of interviews. Because I don't believe it is.

fournm 13y ago
It's certainly useful when you find that someone accidentally made something n^5 instead of n and you need to explain to that person why they were very, very wrong.
- bagels 13y ago
  Yes, this discussion happens with junior engineers. I keep finding O(n^2) code that should have been O(n) or O(n log n), and not just as an academic exercise, because it slows the website down.
  - mmanfrin 13y ago
    You don't code the notation. Knowing how to write optimized code != knowing the notation. I have hardly seen the notation outside interviews.
pjscott 13y ago
I've run into plenty of cases where something was unacceptably, brokenly slow for a handful of inputs, and I wanted to figure out why, and then I realized "Oh, this bit of code is O(n^2) and it's running into a weird edge case with a large n", and then fixed it. I've also run into cases of regular expressions running in exponential time, which is always entertaining.
- mmanfrin 13y ago
  Yes, but you saw code was not optimized, you didn't see the letters "O(n^2)" in the code. I'm not asking why optimization is important, I'm asking about the notation that only seems to appear in interviews.
  - fournm 13y ago
    The notation just happens to give a good shorthand when discussing bits of code, as it tends to be rather fast to calculate.
  - lukeschlather 13y ago
    Big-o is about a specific class of optimization, and a theoretical understanding of it is important. It is important to distinguish between asymptotic optimization vs. i/o optimization vs. code optimization. I'd argue if you can't do the first one you're less likely to be able to handle the next two. Yes, you can do it intuitively to some extent. However, I think it's important to be systematic about it so we can have meaningful conversations about it beyond "doing it this way is slow and if we do it this way it's faster."
nilkn 13y ago
Big-O is an extremely easy way to sum up the running time of an algorithm. Sometimes it's misleading, but usually it's fairly informative, and with most code it can be worked out with just a glance or two. It's so simple and yet still reasonably informative that I'm not sure how it wouldn't be useful.
skywhopper 13y ago
The notation may not be valuable in itself, but the concept is very important.
- mmanfrin 13y ago
  Right, question was about the notation itself -- I understand that optimization is important.
  - zachsnow 13y ago
    It's not that optimization is important, it's that understanding computational complexity is important. Why? Because it tells you when some kinds of optimizations might help, and when they likely will not. It helps you not write inefficient code in the first place, or it lets you use a simple algorithm when it will be sufficiently fast for your needs. If you have a basic understanding complexity you almost certainly have seen and can more or less read the notation, as you probably needed it in order to develop that understanding of complexity in the first place. Whether you really need to understand some of the finer details, if you should have a tattoo of the Master theorem, well, I don't know. ("You" being whoever, not you).
  - overcyn 13y ago
    Your comments appear to be critiquing the existence of the notation itself. I'm not sure what you expect the alternative to be. Words are used to communicate concepts. Knowing the complexity of algorithms is important, correct? How would you go about teaching something like that to a student? Limit yourself to generic terms like linear vs exponential? Would that student have as nuanced an understanding of the subject compared to if he or she learned Big-O notation?
nbm 13y ago
I'm involved in several (20+?) conversations a year where Big-O is used. It's mostly used as a very efficient shorthand for explaining the source of a performance or memory problem (instead of an algorithm being "slow" or "big", it's that it is an algorithm whose performance is acceptable for certain set sizes), and why a particular change is a good fit for the solution. (Then again, I also am involved in a few constant-time optimisation discussions a year, where cache coherency beats out complexity as useful in an algorithm.) I don't expect people to know the notation, but I expect that they can explain the underlying values for a particular algorithm.
Locke1689 13y ago
Discussing the complexity of your solution and deciding if the algorithm is worth focusing on?

It's certainly useful when you find that someone accidentally made something n^5 instead of n and you need to explain to that person why they were very, very wrong.

bagels 13y ago
Yes, this discussion happens with junior engineers. I keep finding O(n^2) code that should have been O(n) or O(n log n), and not just as an academic exercise, because it slows the website down.
- mmanfrin 13y ago
  You don't code the notation. Knowing how to write optimized code != knowing the notation. I have hardly seen the notation outside interviews.

pjscott 13y ago

I've run into plenty of cases where something was unacceptably, brokenly slow for a handful of inputs, and I wanted to figure out why, and then I realized "Oh, this bit of code is O(n^2) and it's running into a weird edge case with a large n", and then fixed it. I've also run into cases of regular expressions running in exponential time, which is always entertaining.

mmanfrin 13y ago
Yes, but you saw code was not optimized, you didn't see the letters "O(n^2)" in the code. I'm not asking why optimization is important, I'm asking about the notation that only seems to appear in interviews.
- fournm 13y ago
  The notation just happens to give a good shorthand when discussing bits of code, as it tends to be rather fast to calculate.
- lukeschlather 13y ago
  Big-o is about a specific class of optimization, and a theoretical understanding of it is important. It is important to distinguish between asymptotic optimization vs. i/o optimization vs. code optimization. I'd argue if you can't do the first one you're less likely to be able to handle the next two. Yes, you can do it intuitively to some extent. However, I think it's important to be systematic about it so we can have meaningful conversations about it beyond "doing it this way is slow and if we do it this way it's faster."

nilkn 13y ago

Big-O is an extremely easy way to sum up the running time of an algorithm. Sometimes it's misleading, but usually it's fairly informative, and with most code it can be worked out with just a glance or two. It's so simple and yet still reasonably informative that I'm not sure how it wouldn't be useful.

skywhopper 13y ago

The notation may not be valuable in itself, but the concept is very important.

mmanfrin 13y ago
Right, question was about the notation itself -- I understand that optimization is important.
- zachsnow 13y ago
  It's not that optimization is important, it's that understanding computational complexity is important. Why? Because it tells you when some kinds of optimizations might help, and when they likely will not. It helps you not write inefficient code in the first place, or it lets you use a simple algorithm when it will be sufficiently fast for your needs. If you have a basic understanding complexity you almost certainly have seen and can more or less read the notation, as you probably needed it in order to develop that understanding of complexity in the first place. Whether you really need to understand some of the finer details, if you should have a tattoo of the Master theorem, well, I don't know. ("You" being whoever, not you).
- overcyn 13y ago
  Your comments appear to be critiquing the existence of the notation itself. I'm not sure what you expect the alternative to be. Words are used to communicate concepts. Knowing the complexity of algorithms is important, correct? How would you go about teaching something like that to a student? Limit yourself to generic terms like linear vs exponential? Would that student have as nuanced an understanding of the subject compared to if he or she learned Big-O notation?

nbm 13y ago

I'm involved in several (20+?) conversations a year where Big-O is used. It's mostly used as a very efficient shorthand for explaining the source of a performance or memory problem (instead of an algorithm being "slow" or "big", it's that it is an algorithm whose performance is acceptable for certain set sizes), and why a particular change is a good fit for the solution. (Then again, I also am involved in a few constant-time optimisation discussions a year, where cache coherency beats out complexity as useful in an algorithm.) I don't expect people to know the notation, but I expect that they can explain the underlying values for a particular algorithm.

Locke1689 13y ago

Discussing the complexity of your solution and deciding if the algorithm is worth focusing on?