[FFmpeg-devel] [PATCH 3/3] avformat/format: av_register_output_format() and av_register_intput_format() that work in O(1) time

Michael Niedermayer michaelni at gmx.at
Tue Dec 17 19:51:53 CET 2013


On Mon, Dec 16, 2013 at 05:20:49PM -0800, Timothy Gu wrote:
> On Dec 16, 2013 4:09 PM, "Michael Niedermayer" <michaelni at gmx.at> wrote:
> > Subject: [FFmpeg-devel] [PATCH 3/3] avformat/format:
> > av_register_output_format() and av_register_intput_format() that
> > work in O(1) time
> 
> Stupid question, what does O(1) mean? I read the Wikipedia article about
> big O notation but it seems so confusing.

it means that independant of some parameter (here the number of
registered elements) theres a upper bound
on the time that the operation takes on average.

for example this is not true for the time it takes to write a mail
in relation to the length of the mail. Theres always a mail that
would be long enough to take more time than any constant bound one
could pick.

OTOH the time it takes to add one letter to a mail is different, even
with a arbitrary huge mail it wont take longer

If you now have multiple people who try to add one letter to the mail
at the same spot (but such contention is assumed to be rare and
negligible) then on average this changes nothing but in rare cases it
could slightly delay one. But as this is assumed to be negligible it
doesnt change the time

-- 
Michael     GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Complexity theory is the science of finding the exact solution to an
approximation. Benchmarking OTOH is finding an approximation of the exact
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 198 bytes
Desc: Digital signature
URL: <http://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20131217/9d9600a4/attachment.asc>


More information about the ffmpeg-devel mailing list