I think O() analysis definitely has its uses. It's good for determining "all else being equal, which algorithm will be faster?" It doesn't say anything about implementations. I'm pretty sure I could write a poor implementation of an O(n log n) algorithm that runs slower than a good implementation of an O(n^2) algorithm (for sufficiently small datasets. How small? Small enough so the O(n log n) implementation is slower :) But in general, the O(n log n) solution will be faster, as your data set increases in size, and as you tweak the "all else" in your implementation to get it as close to "equal" as possible.

I wasn't a huge fan of O() notation in college either, once we started analyzing the more complicated algorithms. Not because it was inaccurate, but because it was difficult, and "no one uses those algorithms anyway." However, now I'm glad I did it, because after doing all the hard analysis, the easy analysis which I do use regularly (though not explicitly) comes intuitively.

Alan

---

---

• Are you posting in the right place? Check out Where do I post X? to know for sure.
• Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:

  <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>

• Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
• Want more info? How to link or How to display code and escape characters are good places to start.