search

smarco / BiWFA-paper

Bidirectional WFA (Paper)
Other
41 stars 3 forks source link

O(n+s^2) expected time #2

Closed RagnarGrootKoerkamp closed 2 years ago

RagnarGrootKoerkamp commented 2 years ago

Myers'86 shows that the diagonal transition method has O(n+s^2) expected time on random strings, and similarly Ukkonen'85 mentions that the O(s * min(n,m)) time is a worst case and at best it uses O(s^2 + min(n,m)) time.

It would be nice if you included a similar statement in your paper, since in practice, it will be very rare to take more than O(n+s^2) time, and I would expect the random-string analysis of Myers'86 to still apply.

I spent some time thinking about this, and while I can indeed come up with cases that would actually need O(ns) time, they are extremely contrived.

smarco commented 2 years ago

Looks convincing to me (and a good idea). I will try to push this statement in the paper.

Thanks for the feedback.