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: fc89c,97188312486d4578 X-Google-Attributes: gidfc89c,public X-Google-Thread: 109fba,baaf5f793d03d420 X-Google-Attributes: gid109fba,public X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public X-Google-Thread: 103376,97188312486d4578 X-Google-Attributes: gid103376,public From: pete@borland.com (Pete Becker) Subject: Re: Teaching sorts [was Re: What's the best language to start with?] Date: 1996/08/22 Message-ID: <4vi565$bhp@druid.borland.com>#1/1 X-Deja-AN: 175862302 distribution: inet references: <4v2qkd$40f@news1.mnsinc.com> <4vd05f$rt5@news1.mnsinc.com> <01bb8f1b$ce59c820$32ee6fce@timhome2> <4vfe33$dg6@druid.borland.com> <4vhm8t$hdg@news1.mnsinc.com> content-type: Text/Plain; charset=ISO-8859-1 organization: Borland International mime-version: 1.0 newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada Date: 1996-08-22T00:00:00+00:00 List-Id: In article <4vhm8t$hdg@news1.mnsinc.com>, huang@mnsinc.com says... > >Pete Becker (pete@borland.com) wrote: >[snip] >: No. The point is that this notation talks about asymptotic behavior, not >: behavior for specific cases. If you want to talk about more complex notions, >: feel free, but don't use O() notation to talk about them, because you will >: confuse people when you misuse this notation. In particular, note that > >: f(x) = 100000*x + x*x > >: is linear for small values of x, and quadratic for large values. O(f(x)) is >: O(x^2), however, because eventually the x^2 term dominates. > >I understand your point, and I agree with you in the strictest technical >sense. However, it doesn't help at all if you tell somebody your >algorithm is O(n) when it's actually O(1000n) in a certain range of >n. O(n) and O(1000n) are EXACTLY THE SAME THING. >Think about it - what do we use time complexity for? As I said earlier, if you want to devise a different notation for talking about algorithmic complexity, feel free to do so. Do not distort existing notation to mean something different from what it has traditionally meant in CS and from what it means in mathematics. >To predict >behavior as n increases from our test case (usually smaller) to our >real case (usually bigger). If the statement of the algorithm does not >make it obvious that f(x) in O(f(x)) is not a continuous function, I >believe it is the failing of the statement. > >IOW, if I test your algorithm for 1,000 inputs and find that it works >fine, then install it for use on my real world 10,000,000 input database, >*and* your documentation doesn't tell me about this "little kink" when >n > 1000, let's just say I probably won't pay you. ;) > If you try to extrapolate the behavior of an implementation of an algorithm to 10,000,000 inputs from the behavior based on the behavior for 1,000 inputs you need something other than O(). >Based on the same reason why we study best, average, and worst case >time complexities of each algorithm, I believe it is important, if not >necessary, that these behaviors are documented along with the time >complexity. Put simply, I expect "O(n) with nothing else" to imply >continuous linear behavior, and special cases such as yours to say >"O(n) from here to there, O(n^2) from here to there". What you "expect" is irrelevant if it is different from the way O(n) is defined. O(n) says that eventually the behavior is linear, not that it is linear everywhere. The idea is to simplify discussions of time complexity in order to improve understanding. Simplifications cannot be relied on to describe full behavior, precisely because they are simplifications.