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: 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: 175908410 references: <4v2qkd$40f@news1.mnsinc.com> <4vd05f$rt5@news1.mnsinc.com> <01bb8f1b$ce59c820$32ee6fce@timhome2> <01bb8f83$e115a340$87ee6fce@timpent.airshields.com> 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 "Perhaps. My understanding of O() notation is that it does not give a prediction of running time, it gives a rough approximation of behavior based on data set size." OK, anyone can have a misunderstanding, but that's what this is, the big-O behavior does NOT give a prediction of running time. For instance you cannot say that an O(N^2) algorithm is worse than an O(N) algorithm, because it might be the case that N has to be too large, or the constant is too great. Here is an example. It is possible to multiply two N digit numbers using an algorithm whose behavior is O (N ** (1 + epsilon)) for any value of epsilon, which sounds as though you can get as close to linear as you like, which is true, but only in the asymptotically limiting case. In practice, if you choose a very small epsilon, then the constant is soo large that this is a very inefficient algorithm. In practice you will prefer even an O(N^2) algorithm to an O(N^1.0000000000001) algorithm constructed in this general manner (although in practice hybrid algorithms like the Toomb-Cooke algorithm -- I hope I spell this right, it is an ancient memory -- dynamically adjust epsilon to get optimal performance for a given value of N, and result in a performance of something like O(N log log N) which doesn't look as good as O(N^1.00000000001) but is in fact faster for any practical data set size. Once again, I refer people to Mike Feldman's book, I think he has a very clear treatment of big_O notation, as well as a good explanation of its importance (despite hints in this thread that it is broken and needs fixing :-)