The Lumber Room

"Consign them to dust and damp by way of preserving them"

Big O() notation: a couple of sources

with one comment

This post contains, just for future reference, a couple of primary sources relevant to the O (“Big O”) notation:

  1. Some introductory words from Asymptotic Methods in Analysis by de Bruijn
  2. An letter from Donald Knuth on an approach to teaching calculus using this notation.


First, a part of section 1.1 (“What is asymptotics?”) and a part of section 1.2 (“The O-symbol”), from Chapter 1 (“Introduction”) of the first edition of the book Asymptotic Methods in Analysis by N. G. de Bruijn (1958)

2

3

4

5

6

7


Second, a letter from Donald Knuth sent to the Notices of the American Mathematical Society, and published in abridged form in the June/July 1998 issue (titled “Teach Calculus with Big O“). Click on any of the images below to download the PDF. (The PDF has been generated by running pdftex ocalc.tex on the original source TeX file ocalc.tex from Knuth’s website.)

You can also see the slightly abridged form that was published (or among other letters directly from the AMS website), and it’s also been typeset and posted at the Mathematics Under the Microscope blog by Alexandre Borovik (note it has a tiny typo there).

ocalc-1

ocalc-2

ocalc-3

Written by S

Thu, 2014-03-13 at 16:33:20

One Response

Subscribe to comments with RSS.

  1. I was going to write some comments in a separate post, but will just leave some links here.

    On Knuth’s idea (which seems good to me), see http://quomodocumque.wordpress.com/2012/05/29/knuth-big-o-calculus-implicit-definitions-difficulty-of/ but also the last two comments by David Speyer.
    And see also http://cornellmath.wordpress.com/2007/08/28/non-nonstandard-calculus-i/ and http://texnicalstuff.blogspot.in/2011/05/big-o-notation-for-calculus.html that seem to have tried teaching along somewhat similar (but different) lines.

    S

    Fri, 2014-03-14 at 02:00:54


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s