- From: Steven Pemberton <steven.pemberton@cwi.nl>
- Date: Wed, 25 Apr 2007 14:56:57 +0200
- To: "Andrew Fedoniouk" <news@terrainformatica.com>, "Ilia Goranov" <css-babailiica@babailiica.com>, www-style@w3.org

On Wed, 25 Apr 2007 06:13:52 +0200, Andrew Fedoniouk <news@terrainformatica.com> wrote: >> Are you sure about this? CSS is currently designed so that you can >> decide when you are at an element which styles apply, and presumably >> implementations use that knowledge. Consequently if you added this rule >> to such implementations it would indeed blow the complexity up. But it >> is not inherent complexity; since the selector ">" and the proposed "<" >> are symmetrical, I would expect at worst only a linear increase in >> complexity. It would just need a different algorithm. > > ...since the selector ">" and the proposed "<" are symmetrical,... > > They are far from being symmetrical. > > A > B - any element B that has immediate parent of A > > So to check for B selector - O(1), > for A selector - O(1) > and "immediate parent" is always known so also O(1). > And integral complexity = O(n) > > A < B - any element A that has B among its n children. > > You need to check for A - O(1). > and all n children for B selector > > n * O(1) + O(1) = O(n) > > So time needed to test for the selector > is dependent from number of children of the element. > > In fact main bottleneck of style resolving > is not selector tests per se. > But in any case selectors that are O(n) complex > where n is a number of children or characters and > not desirable. But this is just what I was saying. If you take the existing implementation algorithms then "<" would increase the complexity. It's like you can't ask "what is the complexity of sorting" only "what is the complexity of this sorting algorithm". Linear sort is O(n^2) but sorting isn't inherently of that order. However, using a different algorithm "<" doesn't need to be more expensive than ">", because they are symmetric (they really are symmetric; your algorithm just requires more time for one than the other). Steven

Received on Wednesday, 25 April 2007 12:57:16 UTC