The problem is that calculus tends to deal with the concept of infinitesimally
small and O(eps) is used for small eps. Computer Science tends to deal with
complexity and O(n) is used for large n. The Big-Oh definitions are different:
i) In calculus f(x) in O(g(x)) iff lim_{x\rightarrow 0} f(x)/g(x) < \infty
ii) In CS f(x) in O(g(x)) iff lim_{x\rightarrow\infty} f(x)/g(x) < \infty
It is common to use (i) to teach calculus (I was thought that way) but it is
not common to use (ii) to teach algorithms. I do so in my notes for Design and
Analysis of Algorithms [1]
and students like it but many computer scientists believe that using limits is
just an extra step.
Massimo
[1]http://bazaar.launchpad.net/%7Emdipierro/algorithms-animator/devel/download/3/csc321notes.pdf-20080914191632-ofooevmsoqqnkrpz-6/csc321notes.pdf?file_id=csc321notes.pdf-20080914191632-ofooevmsoqqnkrpz-6
________________________________________
From: [EMAIL PROTECTED] [EMAIL PROTECTED] On Behalf Of kirby urner [EMAIL
PROTECTED]
Sent: Wednesday, December 10, 2008 10:39 PM
To: [email protected]
Subject: Re: [Edu-sig] computer algebra
On Wed, Dec 10, 2008 at 8:27 PM, Guido van Rossum <[EMAIL PROTECTED]> wrote:
<< SNIP >>
> There are different schools of thought about this actually. I don't
> think pride comes into it.
Well, *my* school is quite pompous about it. We think "open oh" is for sissies.
But that's just us (quirky). Others more sobering.
<< GOOD STUFF >>
>> Note that by "open oh" I'm not talking about "big oh", a different
>> notation that I don't think is redundant, agree with Knuth that if
>> your calculus book doesn't include it, you're probably in one of those
>> computer illiterate schools (ETS slave, whatever).
>
> I think that comment is a little out of line. BTW big Oh is not part
> of calculus, it's part of complexity theory, a totally different field
> (more relevant to computers than calculus though).
>
Not part of calculus as commonly taught today, but *would* be if
Donald Knuth had his way:
http://micromath.wordpress.com/2008/04/14/donald-knuth-calculus-via-o-notation/
Kirby
> --
> --Guido van Rossum (home page: http://www.python.org/~guido/)
>
_______________________________________________
Edu-sig mailing list
[email protected]
http://mail.python.org/mailman/listinfo/edu-sig
_______________________________________________
Edu-sig mailing list
[email protected]
http://mail.python.org/mailman/listinfo/edu-sig
