From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 109fba,baaf5f793d03d420
X-Google-Attributes: gid109fba,public
X-Google-Thread: fc89c,97188312486d4578
X-Google-Attributes: gidfc89c,public
X-Google-Thread: 1014db,6154de2e240de72a
X-Google-Attributes: gid1014db,public
X-Google-Thread: 103376,97188312486d4578
X-Google-Attributes: gid103376,public
From: huang@mnsinc.com (Szu-Wen Huang)
Subject: Re: Teaching sorts [was Re: What's the best language to start with?]
Date: 1996/08/20
Message-ID: <4vd05f$rt5@news1.mnsinc.com>#1/1
X-Deja-AN: 175716436
distribution: inet
references: <4umeot$re2@hil-news-svc-2.compuserve.com>
 <dewar.839831192@schonberg> <4v2fb9$lpj@news.utdallas.edu>
 <4v2qkd$40f@news1.mnsinc.com> <dewar.840305735@schonberg>
followup-to: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada
organization: Monumental Network Systems
newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada
Date: 1996-08-20T00:00:00+00:00
List-Id: <comp.lang.ada>


Robert Dewar (dewar@cs.nyu.edu) wrote:
: "Wrong order.  An O(n) program where n=1,000 that takes 1 second to
: complete should be able to finish n=2,000 in 2 seconds, not the other
: way around.  In other words, you can't derive time complexity by
: timing an algorithm, *especially* with only two samples."

: This statement is wrong (big-O seems to be generating a lot of confusion).
: big-O notation is about asymptotic behavior. If you know an algorithm
: is O(N) and you know that the time for n=1000 is one second, you know
: ABSOLUTELY NOTHING about the time for n=2000, NOTHING AT ALL!

: For example, suppose the behavior of an algorithm is

:   for n up to 1000, time is 1 second

"time is *n* seconds", I presume.  Otherwise this would be O(1).

:   for n greater than 1000, time is 1000*n seconds

: that's clearly O(N), but the time for 2000 items will be 2_000_000
: seconds.
[snip]

I disagree.  I expect a linear algorithm to display linear behavior
unless otherwise stated.  What you cite is a case where it needs to
be explicitly stated, because calling that algorithm "O(n)" is next
to useless in predicting its behavior without knowing this peculiar
behavior at n=1,000.  IOW, this prediction holds if I'm predicting
for n in (0, 1,000] and (1,000, infinity), and will hold for other
algorithms that do not have this peculiarity.