Re^2: Common Perl Pitfalls

Care to elaborate on that "quadratic" comment? How do you figure? I'm not that good with complexity theory, I'm afraid...

Comment on Re^2: Common Perl Pitfalls

Replies are listed 'Best First'.
Re^3: Common Perl Pitfalls by JavaFan (Canon) on Apr 10, 2012 at 13:22 UTC
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² - 2N + 4)/8`. Which means your algorithm runs in `Ω(N²)` time.	[reply]
Re^4: Common Perl Pitfalls by Joe_ (Beadle) on Apr 10, 2012 at 18:10 UTC
Wonderful. Thanks for enlightening me...	[reply]