Python and Schools

[Steven Taschuk]

Quoth Greg Brondo:
  [...]
> 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)?

Others have given good explanations of the usual use of big-O
notation, namely, to describe roughly how the running time of an
algorithm relates to the size of its input.  Imho this is actually
a convenient but slightly sloppy way of speaking; strictly
speaking one counts operations performed.  Roy Smith's excellent
post, for example, focusses on memory copy operations,
essentially; that's a good choice for that problem, while counting
string concatenations would not be, if we're interested in
predicting runtime.

And you can use big-O notation for counting things other than
operations.  For example, it is correct usage to describe a
trade-off as being between, say, an algorithm which runs in O(n)
time but needs O(n^2) memory to do it, and an alternative which
runs in O(n^2) time but only needs O(n) memory.

-- 
Steven Taschuk                  staschuk at telusplanet.net
"Telekinesis would be worth patenting."  -- James Gleick