Very mild disagreement here with For the most part, the monks I see using big O do in fact know what it means and are aware of all or most of the issues involved in it.
in reply to Re: Learning Fundamentals: Data Structures and Algorithm Analysis in Perl
in thread Learning Fundamentals: Data Structures and Algorithm Analysis in Perl
I would say that most of the monks I see using it are aware of how it is used informally by hackers, but a very large fraction are unaware of the formal definition, and/or are unaware of several subtleties that come up fairly often. (I rather strongly suspect that most who are aware that the formal definition probably couldn't come up with a reasonable version of it on demand...)
For instance if someone says, "That's O(1), not O(n)" they are really thinking of big-Omega, not big-O. Because by the formal definition, anything that is O(1) is also O(n). However that's not how hackers informally use the term. And lots of them don't know that their informal usage is technically incorrect.
Furthermore hackers usually have an implicit "amortized average time, if things work like they are supposed to" thrown in that they are not even conscious of. Worse yet, if they were asked to really explain what they meant, most probably couldn't.
For instance most of us accept that, "hash lookup is O(1)." Well actually that's the average case if your hashing algorithm is working properly. The worst case with most hash implementations is O(n). If your hashing algorithm isn't a good fit, you'll hit that worst case fairly often.
And what about that "amortized" bit? Well if you accept that pushing an element is O(1), you've implicitly accepted the amortized bit. If you're doing Perl programming that's OK. If you're doing real-time programming however...
Then of course there is the glaring issue that scalability is often not what matters. For instance which is faster? Scanning a sorted list for an element, or doing a binary search? Despite O(n) vs O(log(n)), in a low-level language on modern CPUs, scanning is probably faster. Very few of us have a good sense for this kind of detail.
As you see there are a lot of issues and complications that come up in a more formal discussion. My suspicion is that a large fraction (and possibility the majority) of Perl hackers who throw around the term aren't really aware of those. They could learn it pretty easily, but don't know it off of the top of their heads. However I'd absolutely agree that their understanding is more than sufficient for a practical analysis of the kinds of problems that we programmers are usually likely to encounter.