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 + 1^{st} iteration, the splicing takes at least N/2  1 steps, as that many array elements need to be moved. On the N/2 + 2^{nd} iteration, the splicing takes at least N/2  2 steps. In total, you will be moving
Σ^{N/21}_{i=1}(i)
array elements. If I've done my math correctly, the above sum equals (N^{2}  2N + 4)/8. Which means your algorithm runs in Ω(N^{2}) time.
