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/2-1}_{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.