[MPlayer-dev-eng] Nut startcodes

[Ville Saari]

On Thu, Apr 29, 2004 at 03:47:01PM -0400, D Richard Felker III wrote:

> No, there is never anything O(n^2). This is total nonsense.

I was not talking about the time to do the actual seek, but the time
to find a keyframe when you have already located the startcode you want to
start at and a frame-accurate seek is needed. The O(n^2) reference was to
the naive algorithm to try the given startcode and if it doesn't work, try
the previous one and if it doesn't work either, then the previous to that
and so on. If you needed to go n startcodes backwards then you had scanned
n^2/2+n/2 startcode distances, which is definitely O(n^2).

That's not to say that it couldn't be done more effciently, but if the
programmer expects to never have to go very far back, then he might
write something like that. I was just trying to point out the difficulties
that might arise if the format allows an arbitrary number of startcodes
between two consecutive keyframes.

-- 
 Ville