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

David Eppstein eppstein at
Wed Apr 16 04:10:40 CEST 2003

In article <b7id3q$3s4$1 at>,
 anton at (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            
Univ. of California, Irvine, School of Information & Computer Science

More information about the Python-list mailing list