Subject: RE: O(n) notation (and character padding) From: "David Bergman" <davidb@xxxxxxx> Date: Fri, 17 Nov 2000 09:00:44 0500 
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 nonexponential algorithms). Wow, this really cleared things up... What this means is the following: 1. The time to complete an nonexponential 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 n1. 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: ownerxsllist@xxxxxxxxxxxxxxxx [mailto:ownerxsllist@xxxxxxxxxxxxxxxx]On Behalf Of Jeni Tennison Sent: Friday, November 17, 2000 5:11 AM To: Dave Gomboc; David Carlisle Cc: XSLList 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 runtime 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="findmax"> <xsl:variable name="greater" select="followingsibling::in[. > current()][1]" /> <xsl:choose> <xsl:when test="$greater"> <xsl:applytemplates select="$greater" mode="findmax" /> </xsl:when> <xsl:otherwise><xsl:valueof select="." /></xsl:otherwise> </xsl:choose> </xsl:template> is 0(n^2) while: <xsl:template match="in" mode="findmax"> <xsl:variable name="maxofrest"> <xsl:applytemplates select="followingsibling::in[1]" mode="findmax" /> </xsl:variable> <xsl:choose> <xsl:when test=". > $maxofrest or not(string($maxofrest))"> <xsl:valueof select="." /> </xsl:when> <xsl:otherwise> <xsl:valueof select="$maxofrest" /> </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/ XSLList info and archive: http://www.mulberrytech.com/xsl/xsllist XSLList info and archive: http://www.mulberrytech.com/xsl/xsllist
Current Thread 


< Previous  Index  Next > 

Re: O(n) notation (and character pa, David Carlisle  Thread  RE: O(n) notation (and character pa, David Bergman 
RE: Splitting result into 2 or more, Linda van den Brink  Date  RE: O(n) notation (and character pa, David Bergman 
Month 