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

[Jeni Tennison <mail@xxxxxxxxxxxxxxxx>]

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