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: 103376,97188312486d4578 X-Google-Attributes: gid103376,public X-Google-Thread: 1014db,6154de2e240de72a X-Google-Attributes: gid1014db,public From: dewar@cs.nyu.edu (Robert Dewar) Subject: Re: Teaching sorts [was Re: What's the best language to start with?] Date: 1996/08/22 Message-ID: #1/1 X-Deja-AN: 175907329 references: <4v2qkd$40f@news1.mnsinc.com> <4vd05f$rt5@news1.mnsinc.com> <01bb8f1b$ce59c820$32ee6fce@timhome2> organization: Courant Institute of Mathematical Sciences newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada Date: 1996-08-22T00:00:00+00:00 List-Id: Tim says "I have to admit, I have to side with Szu-Wen. I've never really thought about this case for the O() notation, but it seems from a purely mathematical standpoint that O(f(n)) means that f(n) is *the* function. If f(n) happens to be a non-continuous function, then so be it. If the running time is kn for n < 1000 k(n^2) for n >= 1000 then f(n) = O(n) for n < 1000 O(n^2) for n >= 1000 then the big-Oh function should be (pardon my syntax) O( (n < 1000) ? n : n^2 ) Well you can side with whoever you like, but big-O notation has a very well accepted meaning, it is about asymptotic behavior, not actual behavbior for any specific finite set of values. If you think that O(N) means that you will see behavior of kN for all N, you are simply mistaken as to the accepted meaning of this notation. If you don't find the accepted meaning useful, fine, but don't try to make up your own personal idiosyncratic definiteion. Your final suggestion is just complete nonsense, since that formula is asymptotically equal to n^2. Asymptotic behavior is an important aspect of analysis of algorithms. It is frequently misunderstood, and lots of poeple think that O(N) means that you will see linear behavior, but it's just wrong, sorry!