Big-O notation (was: Re: Python and Schools)

[David Eppstein]

In article <b7id3q$3s4$1 at news.hccnet.nl>,
 anton at vredegoor.doge.nl (Anton Vredegoor) wrote:

> >Also, one further class that is import to know is O( 2**N ), such as the
> >brute-force solution to the "travelling salesman problem".  These are
> 
> Although it's important to not set too severe limitations I have the
> impression this salesman is underestimating the problem.
> 
> >>> def fac(n):
> ...     return reduce(operator.mul,range(2,n+1),1)
> ... 
> >>> fac(10)
> 3628800
> >>> 2**10
> 1024

Actually, it's possible to solve the traveling salesman problem in time 
O(n 2^n), much better than factorial.  But the solution involves dynamic 
programming and is probably not what Chad N. meant by "brute-force".

-- 
David Eppstein                      http://www.ics.uci.edu/~eppstein/
Univ. of California, Irvine, School of Information & Computer Science