Path: csiph.com!aioe.org!.POSTED!not-for-mail From: =?UTF-8?Q?Arne_Vajh=c3=b8j?= 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: References: 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 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