[XSL-LIST Mailing List Archive Home] [By Thread] [By Date]

RE: O(n) notation (and character padding)

---

---

Jenni,

of course two algorithms can take considerably different times while
having the same complexity. Nobody has denied that.

Again, the complexity of an algorithm is the asymptotic behavior
disregarding any factor of a polynomial degree lower than the
complexity (I am talking non-exponential algorithms). Wow, this really
cleared things up...

What this means is the following:

1. The time to complete an non-exponential algorithm will for
   sufficiently "big" inputs be of the form 'f(x)*exp(x, n)', where x
   is a measure of the size of the input and f(x) is a polynomial of
   (maximum) degree n-1.
   The complexity of the algorithm is thus O(exp(x, n)).
2. The 'f(x)' can be quite big, so even the asymptotic (the "sufficiently
   big" part...) behavior can differ considerably.
3. It takes a while to reach those "sufficiently big inputs" (it might
   never happen, as is often the case for small examples). Up to
   that point, the complexity has little if any influence on the
   completion time.

In the XML case, the size of the input is often just the number of
characters in the file.

There is a bible in algorithms and their complexity. Actually, three.
They are made by Professor Donald Knuth, who is probably one of the
most intelligent individuals in this IT world of ours.

Have fun,

David


-----Original Message-----
From: owner-xsl-list@xxxxxxxxxxxxxxxx
[mailto:owner-xsl-list@xxxxxxxxxxxxxxxx]On Behalf Of Jeni Tennison
Sent: Friday, November 17, 2000 5:11 AM
To: Dave Gomboc; David Carlisle
Cc: XSL-List
Subject: Re: O(n) notation (and character padding)


Dave and David,

Thank you both for your thorough and very helpful explanations and
examples.

It's particularly enlightening for me to see that the relative
complexity of the algorithm does not necessarily mean it's generally
worse - it's always a matter of balancing different criteria for a
particular problem.

Indeed, I think I'm right in saying that you can have two algorithms
that do the same thing in different times but with the same
complexity, so Mike's point that:

  num[not(../num > .)][1]

is still 0(n^2) is a comment about how the run-time of the XPath will
increase as more nums are added: it doesn't matter how much time it
takes or the fact it might stop half way through.

This is one of those conceptual revisions that will take a little time
to sink in for me.  I'm still struggling to see why:

<xsl:template match="in" mode="find-max">
  <xsl:variable name="greater"
                select="following-sibling::in[. &gt; current()][1]" />
  <xsl:choose>
    <xsl:when test="$greater">
      <xsl:apply-templates select="$greater" mode="find-max" />
    </xsl:when>
    <xsl:otherwise><xsl:value-of select="." /></xsl:otherwise>
  </xsl:choose>
</xsl:template>

is 0(n^2) while:

<xsl:template match="in" mode="find-max">
  <xsl:variable name="max-of-rest">
    <xsl:apply-templates select="following-sibling::in[1]"
                         mode="find-max" />
  </xsl:variable>
  <xsl:choose>
    <xsl:when test=". &gt; $max-of-rest or not(string($max-of-rest))">
      <xsl:value-of select="." />
    </xsl:when>
    <xsl:otherwise>
      <xsl:value-of select="$max-of-rest" />
    </xsl:otherwise>
  </xsl:choose>
</xsl:template>

is 0(n).

You both recommend looking at a book on algorithms: do you have any
good ones that you recommend particularly?

Thanks again for your help,

Jeni

---
Jeni Tennison
http://www.jenitennison.com/



 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list


 XSL-List info and archive:  http://www.mulberrytech.com/xsl/xsl-list

---