Re: Select a parrent node with s CSS selector?

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