On Fri, Feb 27, 2009 at 5:10 AM, Steve Holden <st...@holdenweb.com> wrote:
> Chris Rebert wrote:
>> On Thu, Feb 26, 2009 at 10:26 PM, odeits <ode...@gmail.com> wrote:
> [...]
>>> while 'a' in L:
>>> L.remove('a')
>>>
>>> not the most efficient but it works
>>
>> "Not the most efficient"; it's terribly inefficient! It's 2*O(M*N) [M
>> = number of 'a's in L], versus just N. And that's not even accounting
>> for all the extra element movement done by .remove()
>>
> Surely 2*O(M*N) is O(M*N) since constant factors are irrelevant in
> assessing performance order?
Obviously that equivalence is true, but in this case I'm emphasizing
that it's even worse than that when constant factors are taken into
account. Big-O is nice in the abstract, but in the real-world those
constant factors can matter.
In pure big-O, it is indeed O(M*N) vs. O(N)
Including constant factors, the performance is roughly 2*M*N*X [X =
overhead of remove()] vs. N, which makes the badness of the algorithm
all the more apparent.
Cheers,
Chris
--
Follow the path of the Iguana...
http://rebertia.com
--
http://mail.python.org/mailman/listinfo/python-list
