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

[Greg Daley <greg.daley@eng.monash.edu.au>]

Hi Subba,

[cut]
> I agree with your point that there is no ordering requirements for options.
> I feel it as more implementation specific. I think, optimistic way is
> considered in the analysis (like hash list for DNAPrefixList, one LinkID
 > in the LinkIDPrefixList).
> Please correct me, if wrong.
> 
> So, it may be better to consider this also in the similar way.

You're not wrong.

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...

>>Currently it is O(p_r), I think.
> 
> 
> Yes.

Greg