Path: csiph.com!eternal-september.org!feeder.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Andreas Leitgeb <avl@logic.at>
Newsgroups: comp.lang.java.programmer
Subject: Re: Wanted: List of intervals
Date: Mon, 20 Feb 2017 13:30:23 -0000 (UTC)
Organization: A noiseless patient Spider
Lines: 10
Message-ID: <slrnoalruv.pvm.avl@logic.at>
References: <o854lm$f4d$1@Gaia.teknon.de> <o8583e$7tj$1@gioia.aioe.org> <o85ob3$k76$1@Gaia.teknon.de> <o85qrk$hsd$1@gioia.aioe.org> <egu8f3Fd40lU1@mid.individual.net> <o8d5aa$1pve$1@gioia.aioe.org> <o8d5g4$qv5$1@dont-email.me> <o8dp55$ndg$2@gioia.aioe.org> <o8eoe8$vrf$1@dont-email.me>
Reply-To: avl@logic.at
Injection-Date: Mon, 20 Feb 2017 13:30:23 -0000 (UTC)
Injection-Info: mx02.eternal-september.org; posting-host="a9022d26289b485e2a8664b49819fc2f"; logging-data="3437"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX1/bJncNbyZ7gnTJsH36uIwi"
User-Agent: slrn/1.0.2 (Linux)
Cancel-Lock: sha1:BbSDg0sCpzyTuCamlJzene4aXIQ=
Xref: csiph.com comp.lang.java.programmer:36356

Eric Sosman <esosman@comcast-dot-net.invalid> wrote:
> (Also, as Robert Klemme pointed
> out, there's another component to the running time: The final scan
> takes O(listSize) time, independent of the number of intervals and
> the number of "marks.")

this O(listSize) is hardly relevant, if a sufficiently flexible
sparse-implementation is used, that allows you to skim over the
holes between entries at warp-speed.