Python and Schools

[Steve Holden]

"Greg Brondo" <greg at brondo.com> wrote ...
> Aahz wrote:
[...]
> > 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)?
>
These notations are to specify the "order of magnitude" of the run time of
an algorithm. If an algorithm is O(N) and your code runs in 10 seconds on a
list of 100 elements then you might expect it to run in 30 seconds on a list
of 300 elements - in other words, the run time is proportional to N, the
input size.

If the algorithm were O(N^2) then the run time could be expected to increase
with the SQUARE of the input size, meaning that an input of 200 elements
would take 40 seconds and an input of 300 elements would take 90 seconds.

The O() notation is a way of describing algorithmic performance without
getting stuck in the real world: it's assumed that for large enough N the
order effects will dominate, leaving any "trivial" variations in timing lost
in the noise. Thus it's a useful way to predict *roughly* how a given
algorithm will scale.

regards
--
Steve Holden                                  http://www.holdenweb.com/
How lucky am I?      http://www.google.com/search?q=Steve+Holden&btnI=1
Python Web Programming                 http://pydish.holdenweb.com/pwp/