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

 Subject: RE: O(n) notation (and character padding) From: "David Bergman" Date: Fri, 17 Nov 2000 09:06:31 -0500
```Oops,

I forgot that the 'f(x)*exp(x,n)' should be 'f(x)+C*exp(x,n)'. Sorry.
It does not affect the points made, though. Haven't had my morning coffee...

/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,

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 &gt; .)][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?

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

```