http://qs321.pair.com?node_id=760634

Updated: Correcting my vernacular misuse of terms, incorporated useful links from moritz, metaperl, in replies.

I've seen a few questions recently on SOPW that mention algorithmic complexity (as Big O(*) notation) (see Wikipedia Big O Notation, Big-O Notation - What is it good for? and An informal introduction to O(N) notation.

While these original question and replies seem to have some basic knowledge, I personally find wisdom somewhat missing or am merely confused by the O(*) notation and analysis of cases.

Sources of Wisdom

Mark Allen Weiss (http://users.cs.fiu.edu/~weiss/) has authored a series of books entitled Data Structures and Algorithm Analysis. There are versions for Ada, Pascal, Java and C++. Many universities use these books as college textbooks, and I myself have saved Data Structures and Algorithm Analysis in PASCAL and use it to this day even though I only code in Perl.

As one would expect, Wikipedia has an article entitled Computational Complexity Theory that is a more general discussion of this subject than the specific case of O(*)

Basics of Expressing Complexity Measurements

Complexity cannot be expressed as merely an 'algorithms' complexity. One must be clear if one is talking about:

  • an average complexity based on mathematical proof
  • an average complexity based on measurements, whether exhaustive (all cases) or a sample of cases
  • a best-case complexity
  • a worse-case complexity
  • etc...

Therefore, O(*) being tossed out as a bare concept is vaneer glued particle board... it looks beautiful, but is unsuitable for a sturdy boat or a roof. O(*) must not be a veneer of "complexity" tossed over dull and simple questions. It is a formalization of specific 'worst-case' conditions of growth.

Initial conditions and bounds are quite important when discussing complexity. Some algorithms behave differently when tuned differently, or when conditions change. For some discussion (also mentioning Weiss's work) you may refer to Wikipedia's article on Shell Sort which also includes an example of Wikipedia's Algorithm Infobox which could provide a model for including 'facts' when discussing O(*) issues here on PM.

Criticism of "Wise Sounding" RTFM questions

While in no way elitist toward fellow Monks, I personally wish to see the Quality/Node ratio here on PM continue to rise. Therefore, I have to rap a few shoulders with a cane to wake from slumber real wisdom. We must always remain vigilent lest "number of writeups" become the Kismet of XP, rather than XP reflecting the wise output of Monks who employ Zazen (meditation).

Questions to Ponder

Therefore, I put these questions to my Fellow Monks.
  1. What sources of Perl documentation are the best references for Algorithmic Complexity questions?
  2. Are there any good PM nodes discussing the fundamentals of algorithmic analysis? Two good tutorials
  3. Might we need a good Tutorial or Quest written entitled "Data Structures and Algorithm Analysis in Perl" to point drifting monks toward?

Call to Action

Perhaps we need a more coherent effort to address Complexity Analysis to coagulate our vast knowledge toward a more elightening end.

Offer your Answers, fellow monks. However, should no node be found that can bring Satori, what monks would be willing to join me in Sesshin on this subject?

-- Patrick

"Upgrade your gray matter, cause one day it may matter" -- DELTRON 3030