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

 Subject: Re: O(n) notation (and character padding) From: Jeni Tennison 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

```