Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.java.programmer > #36359
| Path | csiph.com!aioe.org!.POSTED!not-for-mail |
|---|---|
| From | Arne Vajhøj <arne@vajhoej.dk> |
| Newsgroups | comp.lang.java.programmer |
| Subject | Re: Wanted: List of intervals |
| Date | Mon, 20 Feb 2017 08:51:31 -0500 |
| Organization | Aioe.org NNTP Server |
| Lines | 47 |
| Message-ID | <o8es92$kdc$1@gioia.aioe.org> (permalink) |
| 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> |
| NNTP-Posting-Host | PBuS014lhzVyHjLbXmo/ZQ.user.gioia.aioe.org |
| Mime-Version | 1.0 |
| Content-Type | text/plain; charset=utf-8; format=flowed |
| Content-Transfer-Encoding | 8bit |
| X-Complaints-To | abuse@aioe.org |
| User-Agent | Mozilla/5.0 (Windows NT 6.1; WOW64; rv:45.0) Gecko/20100101 Thunderbird/45.7.1 |
| X-Notice | Filtered by postfilter v. 0.8.2 |
| Xref | csiph.com comp.lang.java.programmer:36359 |
Show key headers only | View raw
On 2/20/2017 7:47 AM, Eric Sosman wrote: > On 2/19/2017 10:52 PM, Arne Vajhøj wrote: >> On 2/19/2017 5:18 PM, Eric Sosman wrote: >>> If I understand you correctly, the time should be O(n+m) >>> for n intervals containing a total of m bytes. >> >> I would call that O(N) in number of intervals and O(N) >> in interval length. > > I'm not sure why you would use the single symbol N to denote > two entirely different quantities. I think that is what is typical done. Big O is not a calculation formula but a description of characteristics. > (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.") True. That is O(N) in list size. >> Where the sorting solution is O(NlogN) and O(1). >> >>> Memory use >>> would be O(biggestOffset - smallestOffset). >> >> O(N) with some assumptions. > > It's the "some assumptions" that are at issue. If we had some > ham we could have ham and eggs if we had some eggs. The hypothesis was O(N) in number of intervals with some assumptions. If those assumptions are not met then I would expect it to be less than O(N). So that was a worst case assumption. Arne
Back to comp.lang.java.programmer | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-16 21:13 +0000
Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-16 17:11 -0500
Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-17 02:49 +0000
Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-16 22:32 -0500
Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-18 07:28 +0000
Re: Wanted: List of intervals Robert Klemme <shortcutter@googlemail.com> - 2017-02-19 20:02 +0100
Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-19 17:13 -0500
Re: Wanted: List of intervals Eric Sosman <esosman@comcast-dot-net.invalid> - 2017-02-19 17:18 -0500
Re: Wanted: List of intervals Robert Klemme <shortcutter@googlemail.com> - 2017-02-19 23:31 +0100
Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-19 23:00 -0500
Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-19 23:09 -0500
Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-19 22:52 -0500
Re: Wanted: List of intervals Eric Sosman <esosman@comcast-dot-net.invalid> - 2017-02-20 07:47 -0500
Re: Wanted: List of intervals Andreas Leitgeb <avl@logic.at> - 2017-02-20 13:30 +0000
Re: Wanted: List of intervals Arne Vajhøj <arne@vajhoej.dk> - 2017-02-20 08:51 -0500
Re: Wanted: List of intervals Robert Klemme <shortcutter@googlemail.com> - 2017-02-16 23:18 +0100
Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-17 02:54 +0000
Re: Wanted: List of intervals Martin Gregorie <martin@address-in-sig.invalid> - 2017-02-16 23:58 +0000
Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-17 03:30 +0000
Re: Wanted: List of intervals Martin Gregorie <martin@address-in-sig.invalid> - 2017-02-17 12:10 +0000
Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-18 08:06 +0000
Re: Wanted: List of intervals Martin Gregorie <martin@address-in-sig.invalid> - 2017-02-18 13:18 +0000
Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-02-18 19:58 +0000
Re: Wanted: List of intervals Martin Gregorie <martin@address-in-sig.invalid> - 2017-02-18 20:45 +0000
Re: Wanted: List of intervals Eric Sosman <esosman@comcast-dot-net.invalid> - 2017-02-19 10:57 -0500
Re: Wanted: List of intervals Andreas Leitgeb <avl@logic.at> - 2017-02-19 17:36 +0000
Re: Wanted: List of intervals a.laforgia@gmail.com - 2017-02-17 03:13 -0800
Re: Wanted: List of intervals Eric Sosman <esosman@comcast-dot-net.invalid> - 2017-02-17 08:20 -0500
Re: Wanted: List of intervals Roedy Green <inquiry@mindprod.com> - 2017-03-08 01:30 -0800
Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-03-09 19:32 +0000
Re: Wanted: List of intervals Andreas Leitgeb <avl@logic.at> - 2017-03-09 23:05 +0000
Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-03-11 01:40 +0000
Re: Wanted: List of intervals Andreas Leitgeb <avl@logic.at> - 2017-03-11 12:39 +0000
Re: Wanted: List of intervals v_borchert@despammed.com (Volker Borchert) - 2017-03-11 18:15 +0000
Re: Wanted: List of intervals Andreas Leitgeb <avl@logic.at> - 2017-03-11 21:47 +0000
csiph-web