3 ms·

It's great to have a handle on big O but funny I've seen people index to it too much. An algorithm can look "really bad" from Big-O point of view and still be

It's great to have a handle on big O but funny I've seen people index to it too much. An algorithm can look "really bad" from Big-O point of view and still be really good if: it's applied to a small enough input, or it's implemented very efficiently.

windowojji 6y ago
> it's applied to a small enough input The whole point of big-O notation is to analyze algorithms as they're applied to input of size `n` larger than some `n_0`. Of course it's not useful for small inputs - it's explicitly about large inputs. > it's implemented very efficiently On large inputs, it's very hard see how, say, a linear algorithm with a quadratic algorithm regardless of how "efficiently" it's implemented. Assuming you're talking about something like cache friendliness or good register allocation?
- xyzelement 6y ago
  Yeah we are talking about the same thing. I agree that what you are saying is deeply connected to value of Big O. I am just pointing out that people sometimes forget to consider these things.
musingsole 6y ago
Most people jump to an extreme hyperbole instead of the reality what they're grappling with. Big-O is just that algorithmatised. Many software systems must be designed to anticipate orders of magnitude growth in scale. However, I'm not sure about how most software systems grow -- not sure anyone really knows. We all have narratives about it, but it's a small, small subset of projects I know about that have an order of magnitude different number of users than when I first learned about them (other than moving to effectively 0).
NationalPark 6y ago
Yes, it's good to remember that complexity analysis is only a theoretical topic that motivates certain approaches. When performance matters, you measure your program/system and use that as the ultimate guide for your work. Cache locality and branch prediction are two examples of practical issues that the theoretical approach will often ignore.

windowojji 6y ago

> it's applied to a small enough input The whole point of big-O notation is to analyze algorithms as they're applied to input of size `n` larger than some `n_0`. Of course it's not useful for small inputs - it's explicitly about large inputs. > it's implemented very efficiently On large inputs, it's very hard see how, say, a linear algorithm with a quadratic algorithm regardless of how "efficiently" it's implemented. Assuming you're talking about something like cache friendliness or good register allocation?

xyzelement 6y ago
Yeah we are talking about the same thing. I agree that what you are saying is deeply connected to value of Big O. I am just pointing out that people sometimes forget to consider these things.

musingsole 6y ago

Most people jump to an extreme hyperbole instead of the reality what they're grappling with. Big-O is just that algorithmatised. Many software systems must be designed to anticipate orders of magnitude growth in scale. However, I'm not sure about how most software systems grow -- not sure anyone really knows. We all have narratives about it, but it's a small, small subset of projects I know about that have an order of magnitude different number of users than when I first learned about them (other than moving to effectively 0).

NationalPark 6y ago

Yes, it's good to remember that complexity analysis is only a theoretical topic that motivates certain approaches. When performance matters, you measure your program/system and use that as the ultimate guide for your work. Cache locality and branch prediction are two examples of practical issues that the theoretical approach will often ignore.