Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!usenet.stanford.edu!panix!not-for-mail From: Grant Edwards Newsgroups: comp.lang.python Subject: Re: Why is regex so slow? Date: Tue, 18 Jun 2013 20:30:20 +0000 (UTC) Organization: PANIX Public Access Internet and UNIX, NYC Lines: 24 Message-ID: References: NNTP-Posting-Host: dsl.comtrol.com X-Trace: reader1.panix.com 1371587420 4928 64.122.56.22 (18 Jun 2013 20:30:20 GMT) X-Complaints-To: abuse@panix.com NNTP-Posting-Date: Tue, 18 Jun 2013 20:30:20 +0000 (UTC) User-Agent: slrn/1.0.1 (Linux) Xref: csiph.com comp.lang.python:48668 On 2013-06-18, Antoine Pitrou wrote: > Roy Smith panix.com> writes: > > You should read again on the O(...) notation. It's an asymptotic complexity, > it tells you nothing about the exact function values at different data points. > So you can have two O(n) routines, one of which always twice faster than the > other. And you can have two O(n) routines, one of which is twice as fast for one value of n and the other is twice as fast for a different value of n (and that's true for any value of 'twice': 2X 10X 100X). All the O() tells you is the general shape of the line. It doesn't tell you where the line is or how steep the slope is (except in the case of O(1), where you do know the slope is 0. It's perfectly feasible that for the range of values of n that you care about in a particular application, there's an O(n^2) algorithm that's way faster than another O(log(n)) algorithm. [Though that becomes a lot less likely as n gets large.] -- Grant Edwards grant.b.edwards Yow! Where's SANDY DUNCAN? at gmail.com