This is the mail archive of the
xsl-list@mulberrytech.com
mailing list .
Re: O(n) notation (and character padding)
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