Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic

Comment on

( #3333=superdoc: print w/replies, xml ) Need Help??

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 ( 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

In reply to Learning Fundamentals: Data Structures and Algorithm Analysis in Perl by spectre9

Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.
  • Log In?

    What's my password?
    Create A New User
    and all is quiet...

    How do I use this? | Other CB clients
    Other Users?
    Others scrutinizing the Monastery: (4)
    As of 2018-02-19 22:54 GMT
    Find Nodes?
      Voting Booth?
      When it is dark outside I am happiest to see ...

      Results (266 votes). Check out past polls.