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: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public X-Google-Thread: 109fba,baaf5f793d03d420 X-Google-Attributes: gid109fba,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/22 Message-ID: <4vhm8t$hdg@news1.mnsinc.com>#1/1 X-Deja-AN: 175704734 distribution: inet references: <4v2qkd$40f@news1.mnsinc.com> <4vd05f$rt5@news1.mnsinc.com> <01bb8f1b$ce59c820$32ee6fce@timhome2> <4vfe33$dg6@druid.borland.com> 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-22T00:00:00+00:00 List-Id: 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. Think about it - what do we use time complexity for? 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. ;) 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".