Subject: Re: O(n) notation (and character padding) From: Jeni Tennison <mail@xxxxxxxxxxxxxxxx> Date: Fri, 17 Nov 2000 15:26:10 +0000 |
David, Another long message! Are you feeling all right? > well in the first one you first get all the elements bigger than > the current element, then you recurse. Perhaps this is my problem. I can see that a naive implementation that actually went through the entirety of the rest of the list to gather all those that were greater (i.e. 'gets all the elements') would lead to 0(n^2). But in my head (and in Saxon) it stops when it finds the first one that's bigger and doesn't do any more comparisons. So I think the behaviour should be described as: step 1: compare 2 < 1 identify node 2 (one step) now recurse: compare 3 < 2 identify node 3 (one step) and so on, so n steps in total, so 0(n). So in other words, because Mike has told me that: > $x[1] naively requires a comparison on each element of the list to > see if its position is equal to 1 (so it would be O(X)). Saxon just > looks at the first element, which is O(1). I know that the XPath is not a 0(n) XPath but a 0(1) XPath. Therefore although naively the template is 0(n^2) it's actually 0(n). Is the naive method the only one that actually counts? Am I still completely missing the point? Thanks yet again, Jeni --- Jeni Tennison http://www.jenitennison.com/ XSL-List info and archive: http://www.mulberrytech.com/xsl/xsl-list
Current Thread |
---|
|
<- Previous | Index | Next -> |
---|---|---|
Re: O(n) notation (and character pa, David Carlisle | Thread | Re: O(n) notation (and character pa, David Carlisle |
XSLT Debugger, Leena Dasgupta | Date | self axis and attributes, Jeni Tennison |
Month |