Re: [DNA] Info: Computation Time/Space requirements for LinkIdentification schemes

[Subba Reddy <subbareddy@samsung.com>]

Hi Greg,

<cut>

> Previously with hashing, that was the mean case - O(1), as based on
> several existing hashing algorithms.   If there is no known ordering
> on a list of options, then there has to be traversal of the list in
> general.
> 
> While it is on average O(p_r/2), O(p_r/2) is also conventionally noted
> O(p_r).
> 
> That's why I said it was linear...
> 

If traversal is required, I agree with linear. 
What I am saying is, if implementations 
(router side, anyway they are changing RA) can take
advantage by putting LinkID as the first prefix, complexity will come 
down to constant. 
For general case, linear is fine.

Thanks & Regards,
Subba Reddy