Python and Schools

[Jordan McCoy]

The notation O(n) and O(n^2) refers to order notation, a means of
representing the execution time of programs, and in particular,
algorithms that operate over a set of data. The more complete definition
is thus:

The order of an algorithm is O(f n), if a function f and a constant k
exists such that k * f(n) is not more then the execution time of the
algorithm, assuming n is a suitable problem set.

The goal of algorithm development is to achieve O(f n) [or O(n)
abbreviated] as this represents constant execution time; each addition
to the problem set adds a constant amount of time to the execution time.
So, an algorithm that takes, for example, 1 second for n=1 would take
100 seconds for n=100, and so forth.

However, most algorithms can't achieve this: larger problem sets
increase algorithmic complexity and therefore increase execution time at
a greater then constant rate. Two examples:

1. The common but inefficient bubble sort has an order of O(n^2). Since
the bubble sort ends up comparing each set element multiple times to
multiple elements, a sort where n=1000 will require nearly 500,000
comparsions. While the math is somewhat more complex and boring, this
means that each addition to the problem set will result in an
exponential time increase.

2. The more efficient quick sort has an order of O(n * log2 n). Worse
then constant time, but much better then exponential time. Generic
sorting algorithms (those that don't rely on knowing pattern information
inherent in the data) rarely improve upon logarithmic time.

You can find more by searching on 'Order Notation.'

Jordan McCoy

> -----Original Message-----
> From: python-list-admin at python.org 
> [mailto:python-list-admin at python.org] On Behalf Of Greg Brondo
> Sent: Tuesday, April 15, 2003 2:07 PM
> To: python-list at python.org
> Subject: Re: Python and Schools
> 
> 
> Aahz wrote:
> > In article <v9e21mhemm8c2 at corp.supernews.com>,
> > Paul Watson <pwatson at redlinec.com> wrote:
> > 
> >>We need to teach students correct design priciples to build 
> something
> >>greater than what already exists.  We will never get very far if we
> >>require everyone to start with a quark or atom.  Yes, of 
> course we need
> >>some people who design silicon and create microcode.  They 
> will learn
> >>the low-level details what they need to know as they need 
> it.  Knowing
> >>great design and organization principles will enable them 
> to make the
> >>most of it.
> > 
> > 
> > While there's some truth to that, try explaining why the 
> following code
> > is a Bad Idea to someone who has no basic understanding of CS:
> > 
> >     s = ''
> >     for i in range(1000000):
> >         s += str(i)
> > 
> > Knowing the difference between O(N) and O(N^2) is critical 
> to writing
> > even the simplest programs.  OTOH, I do agree with you that 
> focusing on
> > programming as a craft is more important to being a programmer than
> > learning CS.
> 
> I understand why the code is bad (copying the string each time in
> memory as it grows).  However, I've never understood the notation's
> O(N) and O(N2)?
> 
> Thanks,
> Greg Brondo
> 
> -- 
> http://mail.python.org/mailman/listinfo/python-list
>