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 |
In Section
Meditations