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: Matt Austern <austern@isolde.mti.sgi.com>
Subject: Re: Teaching sorts [was Re: What's the best language to start with?]
Date: 1996/08/21
Message-ID: <fxtviec1u7m.fsf@isolde.mti.sgi.com>#1/1
X-Deja-AN: 175618788
references: <4v2qkd$40f@news1.mnsinc.com>
organization: SGI
newsgroups: comp.lang.c,comp.lang.c++,comp.unix.programmer,comp.lang.ada
Date: 1996-08-21T00:00:00+00:00
List-Id: <comp.lang.ada>


"Tim Behrendsen" <tim@airshields.com> writes:

> By "useful", I mean conveying information about the algorithm.  I
> agree with you that in practice the less significant terms may
> be left off the function, i.e. O(n*n + n) is effectively equivalent
> to O(n*n).  But the particular case that started all this was the
> non-continuous case, where one range of (n) produces O(n)
> behavior, and another range produces O(n*n).  In practice, this
> would normally be described exactly as I have just done, but I
> don't think it's either accurate or complete to only declare
> the algorithm O(n*n) if both ranges are possible input data.

Not just "effectively equivalent": identical.  By definition (see, for
example, section 1.2.11 of Knuth) a function f(n) is O(g(n)) if there
exists some positive constant C and some index n0 such that, for all 
n >= n0, |f(n)| <= C |g(n)|.

Given this definition, it's easy to prove that any function f that is
O(n^2 + n) must also be O(n^2).