Python and Schools

[Greg Ewing (using news.cis.dfn.de)]

Jordan McCoy wrote:
> 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

Just a few corrections:

I think you mean "the execution time of the algorithm is not
more than k * f(n)".

> The goal of algorithm development is to achieve ... O(n)
> ... as this represents constant execution time;

No, constant time is O(1) -- i.e. completely independent
of n. You're talking about linear time.

> 1. The common but inefficient bubble sort has an order of O(n^2). ...
 > each addition to the problem set will result in an exponential time
 > increase.

That's called polynomial time, not exponential. Exponential time
is O(a^n) for some a, which is even worse.

> 2. The more efficient quick sort has an order of O(n * log2 n). Worse
> then constant time, but much better then exponential time.

Again, I think you mean polynomial. Although it's better than
exponential time, too!

By the way, you can just write that as O(n * log n). The base
of the log is irrelevant, since it only changes things by a
constant factor.

-- 
Greg Ewing, Computer Science Dept,
University of Canterbury,	
Christchurch, New Zealand
http://www.cosc.canterbury.ac.nz/~greg