http://qs321.pair.com?node_id=964321


in reply to Re^2: Common Perl Pitfalls
in thread Common Perl Pitfalls

Care to elaborate on that "quadratic" comment?
Say you want to delete all elements in the second half of the array. The first N/2 iterations of your loop, no splicing happens. But on the N/2 + 1st iteration, the splicing takes at least N/2 - 1 steps, as that many array elements need to be moved. On the N/2 + 2nd iteration, the splicing takes at least N/2 - 2 steps. In total, you will be moving

ΣN/2-1i=1(i)

array elements. If I've done my math correctly, the above sum equals (N2 - 2N + 4)/8. Which means your algorithm runs in Ω(N2) time.

Replies are listed 'Best First'.
Re^4: Common Perl Pitfalls
by Joe_ (Beadle) on Apr 10, 2012 at 18:10 UTC

    Wonderful. Thanks for enlightening me...