[Edu-sig] computer algebra

[DiPierro, Massimo]

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: edu-sig-bounces+mdipierro=cs.depaul.edu at python.org [edu-sig-bounces+mdipierro=cs.depaul.edu at python.org] On Behalf Of kirby urner [kirby.urner at gmail.com]
Sent: Wednesday, December 10, 2008 10:39 PM
To: edu-sig at python.org
Subject: Re: [Edu-sig] computer algebra

On Wed, Dec 10, 2008 at 8:27 PM, Guido van Rossum <guido at python.org> 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
Edu-sig at python.org
http://mail.python.org/mailman/listinfo/edu-sig